116 条题解
-
0
xuji LV 8 @ 2009-04-13 19:13:36
砸地？？？？？？？？？？？？
砸地？？？？？？？？？？？？
砸地？？？？？？？？？？？？
砸地？？？？？？？？？？？？
砸地？？？？？？？？？？？？
var a:array[-100000000..100000000,-100000000..100000000] of byte;
s1,s11,s2,s22,h1,h11,h2,h22,i,j,n,l:longint;
begin
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
begin readln(s1,h1,s2,h2);
for l:=s1 to s2 do
for n:=h1 to h2 do a[l,n]:=1;
if s1s22 then s22:=s2;
if h1h22 then h22:=h2;
end;
j:=0;
for l:=s11 to s22 do
for n:=h11 to h22 do j:=a[l,n]+j;
writeln(j);
end. -
0
经验：
long long a;
long b,c;
a=b*c;
b*c>long int的话
a也会算错这题简单二维离散化
但是注意数据类型
为此我WA了4次
郁闷
ac率啊编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include
#include
using namespace std;
struct mydate{
long date;
long high;
long low;
long id;
};
mydate dx[1005];
long dxn;
long dy[1005];
long dyn;
long n;long long ans;
void init()
{
long i,j;
long x1,y1,x2,y2;
cin >> n;
for(i=1;i> x1 >> y1 >> x2 >> y2;
dx[++dxn].date=x1;
dx[dxn].id=1;
dx[dxn].high=y2;
dx[dxn].low=y1;dx[++dxn].date=x2;
dx[dxn].id=2;
dx[dxn].high=y2;
dx[dxn].low=y1;dy[++dyn]=y1;
dy[++dyn]=y2;}
qsort(1,dxn);
qsort2(1,dyn);
for(i=1;i -
0
JackDavid127 LV 10 @ 2009-03-27 21:37:49
终于对了……
以前看黑书上写《火星地图》要用离散化+二维线段树，看着就晕，干脆放弃……
下午考试又考到了，想用离散化，但没用，光考虑另一题，时间耗费光了~~~~
晚上下定决心：一定要把这题做出来！
终于，AC了！！解法：
离散化，将图划成(2n-1)^2个矩形再分别求面积。
结论：离散+long long+iostream=Accepted -
0
离散化+二分查找=AC
Main code：
Begin
readln(n);
for i:=1 to n do
begin
readln(l[2*i-1],r[2*i-1],l,r);
s:=l[2*i-1];
s:=r[2*i-1];
s:=l[2*i];
s:=r[2*i];
end;
qsort(l,1,2*n);
qsort(r,1,2*n);
for i:=2 to 2*n do
for j:=2 to 2*n do
e:=int64(l[i]-l)*int64(r[j]-r[j-1]);
for i:=1 to n do
begin
x1:=find(l,s);
y1:=find(r,s);
x2:=find(l,s);
y2:=find(r,s);
for j:=x1+1 to x2 do
for k:=y1+1 to y2 do
begin
inc(ans,e[j,k]);
e[j,k]:=0;
end;
end;
writeln(ans);
End. -
0
Prince Frost LV 10 @ 2009-02-18 21:54:14
纯离散化+int64=AC+0ms
以RP担保第四个数据无误 -
0
MD调试中打印的废话又没删掉 0分
if t=0 then begin s:=s+(rx-lx)*(ry-ly);writeln(s);exit; end;
删掉就A了
关于第四个点的问题很多人错误的原因已经被我发现了
我是用矩形切割做的
function check(lx,ly,rx,ry:int64):boolean;
begin
if (rx>lx)and(ry>ly) then exit(true) else exit(false);
end;
程序中加上这个CHECK函数就A 去掉第四个点错
大家可以看记录
在切割的时候要保证矩形仍然存在! -
0
ufo172849z LV 10 @ 2009-01-25 10:55:59
注意算面积的时候不能直接乘，要用int64中转（我因此WA了3次）。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms第240个 AC
本题的第4个数据有误，矩形切割写不出答案，但离散化可以全对。
另外，我挂了N次，各位要注意：
读入数据不仅要int64读入，而且需要注意的是：int64类型的数组元素不能直接读入。。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms基本思想是离散化
1 对读入的每个矩形的左下方与右上方的横纵坐标分别保存在数组zx,zy,yx,yy中。
for i:=1 to n do
readln(zx[i],zy[i],yx[i],yy[i]);
2 因为zx,zy,yx,yy中的横纵坐标有重复，所以把其中的横纵不重复的放在数组x、y 中。（计算前可先升序排序）。x[0] 表示不重复的横坐标的个数,y[0]表示不重复的纵坐标的个数
3 依次枚举(i,j)的坐标是否在原先矩形的区域内，如果在就将f置为true
(f表示的是一个区域)
for i:=1 to n do
for xt:=1 to x[0]-1 do
for yt:= to y[0]-1 do
if (x[xt]>=zx[i])and(x[xt+1]=zy[i])and(y[yt+1] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms第4点好象没错
-
0
fammiebright LV 9 @ 2008-10-01 10:19:38
楼上的骗人，不用cheat。我自己发明的矩形切割，全0ms
存坐标的数组应该开到int64，但是如果想省空间可以用int64的中间变量存两个坐标差，再在ans上相加就行了。
原因是乘法运算优先级比赋值运算高，执行ans:=(x2-x1)*(y2-y1)这条语句时先把乘积赋给x1,x2,y1,y2的数据类型再赋值给ans，造成了数据溢出
xuji
LV 8
@ 2009-04-13 19:13:36
