- 图形面积
- 2016-03-12 18:17:45 @
各位大神,帮我看一下有什么问题,好吗
c++
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=550;
double x[N],y[N],a[N],t[N];
int c[N],n,p[N];
double L,ans;
bool cmp(int a,int b)
{
return y[a]<y[b];
}
void add(double l,double r)
{
int k=upper_bound(a,a+2*n-1,l)-a;
while(a[k]<r&&k<2*n-1)
{
if(c[k]==0)L+=t[k+1]-t[k];
c[k]++;
k++;
}
}
void del(double l,double r)
{
int k=upper_bound(a,a+2*n-1,l)-a;
while(a[k]<r&&k<2*n-1)
{
c[k]--;
if(c[k]==0)L-=t[k+1]-t[k];
k++;
}
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
L=0;
ans=0;
for(int i=0;i<n*2;i++)
scanf("%lf%lf",&x[i],&y[i]);
memcpy(t,x,sizeof(t));
sort(t,t+n*2);
for(int i=0;i<n*2-1;i++)
a[i]=(t[i]+t[i+1])/2.0;
for(int i=0;i<2*n;i++)
p[i]=i;
sort(p,p+2*n,cmp);
memset(c,0,sizeof(c));
for(int i=0;i<2*n;i++)
{
if(i>0)ans+=L*(y[p[i]]-y[p[i-1]]);
if(!(p[i]&1))
add(x[p[i]],x[p[i]^1]);
else del(x[p[i]^1],x[p[i]]);
}
printf("%.0lf\n",ans+0.4);
}
return 0;
}
1 条评论
-
doc LV 10 MOD @ 2016-03-12 20:00:40
别用double,用long long试试。答案不会超过64位符号整数的,所以x,y,ans都用long long试试看。
- 1