WA#6,莫名其妙,第六个位数挂掉应该是精度问题。
开 long double 要么 WA 要么 T。
BZOJ 上数据都能过我你谷不能下载心寒了……
以下是代码(码风勿喷):
#include <bits/stdc++.h>
#define I inline
using namespace std;
const int N=10005;
const double eps=1e-12;
struct Point{
double x,y;
Point(double x=0,double y=0): x(x),y(y) {}
} a[N][5],b[N*10];
bool cmp1(Point x,Point y){ return x.y==y.y?x.x<y.x:x.y<y.y; }
bool cmp2(Point x,Point y){ return x.x==y.x?x.y<y.y:x.x<y.x; }
double ans,last,now,x[N],y[N*10];
int b0,yc;
bool flag;
typedef Point Vector;
Point read_Point(){
double xx,yy;
scanf("%lf%lf",&xx,&yy);y[++yc]=yy;
return Point(xx,yy);
}
Vector operator + (Vector a,Vector b){ return Vector(a.x+b.x,a.y+b.y); }
Vector operator - (Vector a,Vector b){ return Vector(a.x-b.x,a.y-b.y); }
Vector operator * (Vector a,double p){ return Vector(a.x*p,a.y*p); }
Vector operator / (Vector a,double p){ return Vector(a.x/p,a.y/p); }
int dcmp(double x){ if(fabs(x)<eps) return 0; return x<0?-1:1; }
bool operator == (Vector a,Vector b){ return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y); }
double Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }
double L(Vector a){ return sqrt(Dot(a,a)); }
double Angle(Vector a,Vector b){ return acos(Dot(a,b)/L(a)/L(b)); }
double Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }
double Area(Point a,Point b,Point c){ return Cross(c-a,b-a); }
Vector rotate(Vector a,double rad){
return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Vector Normal(Vector a){ return Vector(-a.y/L(a),a.x/L(a)); }
Point InterLineSection(Point P,Vector v,Point Q,Vector w){
Vector u=P-Q;
double t=Cross(w,u)/Cross(v,w);
return P+v*t;
}
void Get(Vector A,Vector B,Vector C,double yy){
if(!dcmp(A.y-C.y)||!dcmp(B.y-C.y)) return;
Vector v1=InterLineSection(A,C-A,Vector(0,yy),Vector(1,0));
Vector v2=InterLineSection(B,C-B,Vector(0,yy),Vector(1,0));
if(v1.x>max(C.x,A.x)||v1.x<min(C.x,A.x)||v2.x>max(B.x,C.x)||v2.x<min(B.x,C.x))
return;
b[++b0]=Vector(min(v1.x,v2.x),max(v1.x,v2.x));
}
int main(){
// freopen("6.in","r",stdin);
int n,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i][1]=read_Point(),a[i][2]=read_Point(),a[i][3]=read_Point();
for (int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=3;k++)
for(int l=1;l<=3;l++)
if(dcmp(Cross(a[i][k==3?1:k+1]-a[i][k],a[j][l==3?1:l+1]-a[j][l])))
y[++yc]=InterLineSection(a[i][k],a[i][k==3?1:k+1]-a[i][k],
a[j][l],a[j][l==3?1:l+1]-a[j][l]).y;
sort(y+1,y+yc+1,cmp1);
for(int i=1;i<=yc;i++){
if(y[i]==y[i-1]&&i!=1)continue;
b0=0;
for(int j=1;j<=n;j++){
Get(a[j][1],a[j][2],a[j][3],y[i]);
Get(a[j][2],a[j][3],a[j][1],y[i]);
Get(a[j][3],a[j][1],a[j][2],y[i]);
}
sort(b+1,b+b0+1,cmp2);
double from=-0x7f7f7f7f;
for(int j=1;j<=b0;j++)
if(b[j].x>from)now+=b[j].y-b[j].x,from=b[j].y;
else if(b[j].y>from)now+=b[j].y-from,from=b[j].y;
if(flag&&b0)ans+=(now+last)*(y[i]-y[i-1])/2;
else if(b0) flag=1;
last=now,now=0;
}
printf("%.2lf\n",ans);
return 0;
}