这T用线段树太大材小用了吧``毕竟n只有100...

---|---|---|---|

啊啊啊!....

我承认都是快排惹的祸...

为什么只能x=i不能x=(i+j)div 2...

还有..YaoMing的第四个点..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

离散

注意精度~~

离散化+线段树~~~~

我的矩形切割。。挂了。。ms老超界。。

比Timus1147("Shaping Regions")弱多了。

离散哈...但是用割法(也不知道叫什么)也行哈..

离散+统计

顺便测试了一下插入排序的效率

补充一下

我写的插入排序向来用move...

离散统计+高精

bubble sort也可以

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;

struct node
{
int x1,y1,x2,y2;
}a[101];

bool cmp(int a,int b)
{
return a<b;
}

int x[201],y[201];
bool b[201][201];

int main()
{
int n;
cin>>n;
int i=0;
while (i<n)
{
i++;
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
if (a[i].x1>=a[i].x2 || a[i].y1>=a[i].y2)
{
i--;
n--;
}
else
{
x[i*2-1]=a[i].x1;
x[i*2]=a[i].x2;
y[i*2-1]=a[i].y1;
y[i*2]=a[i].y2;
}
}
sort(x+1,x+2*n+1,cmp);
sort(y+1,y+2*n+1,cmp);
memset(b,0,sizeof(b));
for (int i=1;i<=n;i++)
for (int j=1;j<2*n;j++)
if (a[i].x1<=x[j]&&a[i].x2>=x[j+1])
for (int k=1;k<2*n;k++)
if (a[i].y1<=y[k]&&a[i].y2>=y[k+1])
b[j][k]=1;
long long s=0;
for (int i=1;i<2*n;i++)
for (int j=1;j<2*n;j++)
if (b[i][j]==1)
s+=(long long)(x[i+1]-x[i])*(long long)(y[j+1]-y[j]);
cout<<s<<endl;
}

#include<stdio.h>
long long x1[200],x2[200],y1[200],y2[200];
int n;
long long res=0;
void flo(long long l,long long r,long long b,long long t,int k)//k:用来切割的矩形
{
if((l>=r)||(b>=t)) return;
while((k>=1)&&(l>=x2[k]||r<=x1[k]||b>=y2[k]||t<=y1[k])) k--;
if(k==0) { res+=(r-l)*(t-b); return;}
if(l<x1[k]) {flo(l,x1[k],b,t,k);l=x1[k];}
if(r>x2[k]) {flo(x2[k],r,b,t,k);r=x2[k];}
if(b<y1[k]) {flo(l,r,b,y1[k],k);b=y1[k];}
if(t>y2[k]) {flo(l,r,y2[k],t,k);t=y2[k];}
return;
}
int main()
{
int i,k;
scanf("%d",&n);
for(i=1;i<n+1;i++)
scanf("%I64d %I64d %I64d %I64d",&x1[i],&y1[i],&x2[i],&y2[i]);
for(i=1;i<n+1;i++)
flo(x1[i],x2[i],y1[i],y2[i],i-1);
printf("%I64d",res);
return 0;
}

醉了，这里Ac了，在学校的系统死活AC不了，我选择死亡。

#include<bits/stdc++.h>
#define maxn 110
using namespace std;
struct Rect{
int x1,x2,y1,y2;
bool read(){//处理错误数据
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
return x1<=x2&&y1<=y2;
}
// void print(){printf("%d %d %d %d\n",x1,y1,x2,y2);}
};

int N;
Rect rect[maxn];

bool table[maxn*2][maxn*2];
void SOLVE()
{
vector<int> x,y;
for(int i=0;i<N;i++)
x.push_back(rect[i].x1),x.push_back(rect[i].x2),y.push_back(rect[i].y1),y.push_back(rect[i].y2);
sort(x.begin(),x.end());
sort(y.begin(),y.end());
x.erase(unique(x.begin(),x.end()),x.end());
y.erase(unique(y.begin(),y.end()),y.end());

int xn=x.size(),yn=y.size();

//for(int i=0;i<xn;i++) printf("%d ",x[i]);puts("");
//for(int j=0;j<yn;j++) printf("%d ",y[j]);puts("");

//离散化
map<int,int> mx,my;
for(int i=0;i<xn;i++) mx[x[i]]=i;
for(int i=0;i<yn;i++) my[y[i]]=i;

for(int k=0;k<N;k++)
for(int i=mx[rect[k].x1];i<mx[rect[k].x2];i++)
for(int j=my[rect[k].y1];j<my[rect[k].y2];j++)
table[i][j]=true;

//计算
int64 ans=0;
for(int i=0;i<xn;i++)
for(int j=0;j<yn;j++)
if(table[i][j])
ans+=(int64)((x[i+1]-x[i]))*(y[j+1]-y[j]);

printf("%I64d\n",ans);
}

void INPUT()
{
int n;
scanf("%d",&n);
while(n--){
if(rect[N].read()) N++;
}

//for(int i=0;i<N;i++) rect[i].print();
}

void MAIN()
{
INPUT();
SOLVE();
}

int main()
{
//freopen("in#pro.txt","r",stdin);
//freopen("out#pro.txt","w",stdout);
MAIN();
return 0;
}

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;
max: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
max:=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;
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
max:=max+ord(map[i,j])*dx[i]*dy[j];
writeln(max);
end.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct point
{
int x,y;
}l[200],r[200],ll[200],rr[200];
int main()
{
int b1[202][202],b2[202][202];
int xp[202],xt[202];
int yp[202],yt[202];
int i,j,k,m,n,count;
long long ans,a1,a2;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d%d%d",&l[i].x,&l[i].y,&r[i].x,&r[i].y);
xp[2*i-1]=l[i].x;
xp[2*i]=r[i].x;
yp[2*i-1]=l[i].y;
yp[2*i]=r[i].y;
}
for (i=1;i<=2*n;i++)
for (j=i+1;j<=2*n;j++)
{
if (xp[i]>xp[j])
{
m=xp[i];xp[i]=xp[j];xp[j]=m;
}
if (yp[i]>yp[j])
{
m=yp[i];yp[i]=yp[j];yp[j]=m;

}
}
for (i=1;i<=n;i++)
for (j=1;j<=2*n;j++)
{
if (l[i].x==xp[j]) ll[i].x=j;
if (l[i].y==yp[j]) ll[i].y=j;
if (r[i].x==xp[j]) rr[i].x=j;
if (r[i].y==yp[j]) rr[i].y=j;
}
memset(b1,0,sizeof(b1));
memset(b2,0,sizeof(b2));
for (i=1;i<=n;i++)
for (j=ll[i].y;j<rr[i].y;j++)
{
b1[ll[i].x][j]++;

b2[rr[i].x-1][j]++;
}

ans=0;
for (i=1;i<2*n;i++)
{
count=0;
for (j=1;j<2*n;j++)
{
count+=b1[j][i];
if (count)
{
a1=xp[j+1]-xp[j];
a2=yp[i+1]-yp[i];
ans+=a1*a2;
}
count-=b2[j][i];
}
}
printf("%I64d\n",ans);
//system("pause");

return 0;
}

这题第一反应就是矩形切割，虽然矩形切割好久没写差不多忘了，但是离散化我很少写，就用离散化写。
不得不说写得很长很丑，比别人的代码长得多。先离散化，然后用括号法。括号法多括了1行、数组太多乱掉打错，导致调试了很久。

描述
桌面上放了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。
格式
输入格式

输入第一行为一个数N（1≤N≤100），表示矩形的数量。下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–10^8到10^8之间的整数。
输出格式

输出只有一行，一个整数，表示图形的面积。