116 条题解
-
-1
freefood LV 10 @ 2015-02-21 15:35:00
呵呵……第四个点……矩形不合法（就是y1>y2），然后不合法就不要算（我竟然傻逼去判断一下y1>y2的话就swap(y1,y2))
-
-1
xyf1996xyf LV 7 @ 2014-05-07 10:04:09
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define MAXn 100
using namespace std;
int n;
long long x1[MAXn+1],y1[MAXn+1];
long long x2[MAXn+1],y2[MAXn+1];
long long x[2*MAXn+1],y[2*MAXn+1];
long long S,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%I64d%I64d%I64d%I64d",&x1[i],&y1[i],&x2[i],&y2[i]);
x[2*i-1]=x1[i];
x[2*i]=x2[i];
y[2*i-1]=y1[i];
y[2*i]=y2[i];
}
sort(x+1,x+2*n+1);
sort(y+1,y+2*n+1);
for(int i=1;i<=2*n-1;i++)
for(int j=1;j<=2*n-1;j++)
{
S=(x[i+1]-x[i])*(y[j+1]-y[j]);
for(int k=1;k<=n;k++)
if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])
{
ans+=S;
break;
}
}
printf("%I64d",ans);
return 0;
} -
-1
program rec;
type
tarr=array[1..300]of int64;
var
map:array[1..300,1..300]of boolean;
x,y:array[1..300]of int64;
dx,dy:array[1..300]of int64;
px,py:array[1..300]of int64;
n,i,j,k:longint;
ans:qword;
function fx(i:longint):longint;
var
j:longint;
begin
for j:=1 to 2*n do
if i=px[j] then
exit(j);
end;
function fy(i:longint):longint;
var
j:longint;
begin
for j:=1 to 2*n do
if i=py[j] then
exit(j);
end;
procedure qsort(l,r:longint; var a,p:tarr);
var
i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=a[(i+j) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if not (i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=p[i];
p[i]:=p[j];
p[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then
qsort(l,j,a,p);
if i<r then
qsort(i,r,a,p);
end;
begin
fillchar(map,sizeof(map),false);
ans:=0;
read(n);
for i:=1 to n do
begin
read(x[i*2-1],y[i*2-1],x[i*2],y[i*2]);
if (y[i*2-1]>y[i*2]) and (x[i*2-1]>x[i*2]) then
begin
x[i*2-1]:=0;
x[i*2]:=0;
y[i*2-1]:=0;
y[i*2]:=0;
continue;
end;
px[i*2-1]:=i*2-1;
px[i*2]:=i*2;
py[i*2-1]:=i*2-1;
py[i*2]:=i*2;
end;
qsort(1,n*2,x,px);
qsort(1,n*2,y,py);
for i:=1 to n*2-1 do
dx[i]:=x[i+1]-x[i];
for i:=1 to n*2-1 do
dy[i]:=y[i+1]-y[i];
for i:=1 to n do
for j:=fx(i*2-1) to fx(i*2)-1 do
for k:=fy(i*2-1) to fy(i*2)-1 do
map[j,k]:=true;
for i:=1 to n*2 do
for j:=1 to n*2 do
ans:=ans+ord(map[i,j])*dx[i]*dy[j];
writeln(ans);
end. -
-1
Reticent、罪 LV 7 @ 2014-01-26 17:04:53
type arr=array[0..10000] of int64;
var x,y,x1:arr;
a:array[1..10000,1..4] of int64;
f:array[1..200,1..200] of boolean;
ans:int64;
n,i,j,k:longint;
procedure qsort(x,y:longint;var a:arr);
var i,j,h:longint;
begin
i:=x;j:=y;h:=a[i];
repeat
while (i<j)and(a[j]>h) do
j:=j-1;
if i<j then
begin
a[i]:=a[j];
i:=i+1;
end;
while (i<j)and(a[i]<h) do
i:=i+1;
if i<j then
begin
a[j]:=a[i];
j:=j-1;
end;
until i>=j;
a[i]:=h;
if i-1>x then
qsort(x,i-1,a);
if i+1<y then
qsort(i+1,y,a);
end;
begin
readln(n);
for i:=1 to n do
begin
readln(a[i,1],a[i,2],a[i,3],a[i,4]);
x[2*i-1]:=a[i,1];x[2*i]:=a[i,3];
y[2*i-1]:=a[i,2];y[2*i]:=a[i,4];
end;
qsort(1,2*n,x);
qsort(1,2*n,y);
x1:=x;j:=2;
for i:=2 to 2*n do
if x1[i]<>x[j-1] then
begin
x[j]:=x1[i];
j:=j+1;
end;
x[0]:=j-1;
x1:=y;j:=2;
for i:=2 to 2*n do
if x1[i]<>y[j-1] then
begin
y[j]:=x1[i];
j:=j+1;
end;
y[0]:=j-1;
fillchar(f,sizeof(f),false);
for k:=1 to n do
for i:=1 to x[0]-1 do
for j:=1 to y[0]-1 do
if (x[i]>=a[k,1])and(x[i+1]<=a[k,3])and(y[j]>=a[k,2])and(y[j+1]<=a[k,4]) then
f[i,j]:=true;
for i:=1 to x[0]-1 do
for j:=1 to y[0]-1 do
if f[i,j] then
ans:=ans+(x[i+1]-x[i])*(y[j+1]-y[j]);
writeln(ans);
end. -
-1
表示漂浮法真尼玛牛B啊
注意以下几点
1. 坐标统统INT64（不要问我为什么，血的教训）
2. 答案开QWORD（坐标都INT64了= =）
3. 注意有些图形无效
写个判断
procedure init;
begin
readln(n);
j:=0;
for i:=1 to n do
begin
inc(j);
readln(x1[j],y1[j],x2[j],y2[j]);
if(x1[j]>=x2[j])or(y1[j]>=y2[j])then dec(j);
end;
end;
4.再次表示（n2）的漂浮法真心牛啊 -
-1
尼玛被long long 坑了两次— —，，很弱的离散。。
评测结果
编译成功foo.cpp: In function 'int find(int, int)':
foo.cpp:11:16: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
测试数据 #0: Accepted, time = 15 ms, mem = 696 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 696 KiB, score = 10
测试数据 #2: Accepted, time = 11 ms, mem = 692 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 696 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 692 KiB, score = 10
测试数据 #5: Accepted, time = 11 ms, mem = 696 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 700 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 700 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 696 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 700 KiB, score = 10
Accepted, time = 37 ms, mem = 700 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
int n,x[201],y[201],c[201][201];
long long d[2][202],r=0;
int find(int q,int f) {
int l=1,r=2*n,m;
while (l<=r) {
m=(l+r)/2;
if (d[f][m]>q) r=m-1; else
if (d[f][m]<q) l=m+1; else break;
} return m;
}
int main(){
scanf("%d",&n);
for (int i=1; i<=n ; i++) scanf("%d%d%d%d",&x[i],&y[i],&x[i+n],&y[i+n]);
for (int i=1; i<=2*n; i++) { d[0][i]=x[i]; d[1][i]=y[i];}
std::sort(d[0]+1,d[0]+1+2*n);std::sort(d[1]+1,d[1]+1+2*n);
for (int i=1; i<=2*n; i++) x[i]=find(x[i],0);
for (int i=1; i<=2*n; i++) y[i]=find(y[i],1);
for (int z=1; z<=n ; z++)
for (int i=x[z]+1; i<=x[z+n]; i++)
for (int j=y[z]+1; j<=y[z+n]; j++) c[i][j]=1;
for (int i=2; i<=2*n; i++)
for (int j=2; j<=2*n; j++)
if (c[i][j]) r+=(d[0][i]-d[0][i-1])*(d[1][j]-d[1][j-1]);
printf("%I64d",r);
} -
-1
漂浮法（N2）全过，比离散（N3）优，晒下主的，不和法的要删掉的。否则第4wa
procedure cover(l,r,d,s,k:int64);
begin
while (k<=n)and((r>=y2[k])or(s<=y1[k])or(l>=x2[k])or(d<=x1[k]))
do inc(k);
if k>n then begin sum:=sum+(d-l)*(s-r);exit;end;
if r<=y1[k] then begin cover(l,r,d,y1[k],k+1);r:=y1[k];end;
if s>=y2[k] then begin cover(l,y2[k],d,s,k+1);s:=y2[k];end;
if d>=x2[k] then begin cover(x2[k],r,d,s,k+1);d:=x2[k];end;
if l<=x1[k] then begin cover(l,r,x1[k],s,k+1);l:=x1[k];end;
end; -
-1
-
-1
program planting;
var
i,j,n,x1,y1,x2,y2,x,y:longint;
ans:int64;
a,b:array[-10000..10000] of boolean;
begin
assign(input,'planting.in');
reset(input);
assign(output,'planting.out');
rewrite(output);
read(n);
for i:=1 to n do
begin
read(x1,y1,x2,y2);
x:=0;
y:=0;
for j:=x1 to x2 do if a[j] then inc(x) else a[j]:=true;
for j:=y2 to y1 do if b[j] then inc(y) else b[j]:=true;
if x>0 then dec(x);
if y>0 then dec(y);
ans:=ans+(x2-x1)*(y1-y2)-x*y;
end;
writeln(ans);
close(input);
close(output);
end. -
-1
lijian3256 LV 10 @ 2009-04-02 15:00:51
又一次cheat了一个数据
我已经不知道是我的问题 还是VJ的问题了
定义成RP差吧。。。失败。。。 -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
经过无数次WA，终于...... -
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
离散就够了。
这数据实在太弱。。。
freefood
LV 10
@ 2015-02-21 15:35:00
