来提供依据hack数据?
查看原帖
来提供依据hack数据?
143541
K0u1e楼主2020/8/30 16:44

数据见底部,我自己的这份AC代码输出了-0.250

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
double eps = 1e-8;
int sgn(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1; }
struct Point{
    double x,y;
    Point(){ x=y=0; }
    Point(double _x, double _y){ x=_x,y=_y; }
    Point operator + (const Point &b) const{ return Point(x+b.x,y+b.y); }
    Point operator - (const Point &b) const{ return Point(x-b.x,y-b.y); }
    Point operator * (double p) const{ return Point(x*p,y*p); }
    Point operator / (double p) const{ return Point(x/p,y/p); }
};
double Cross(const Point &a, const Point &b) { return a.x*b.y-a.y*b.x; }
struct Line{
    Point p,v;
    double ang;
    Line(){}
    Line(Point _p,Point _v){
        p=_p,v=_v; ang=atan2(v.y,v.x);
    }
    bool operator < (const Line &l) const {
        return ang<l.ang;
    }
};
bool Left(const Point &p,const Line &l){
    return Cross(l.v,p-l.p)>=0;
}
Point intersection(const Line &a,const Line &b) {
    Point x=a.p-b.p; double t=Cross(b.v,x)/Cross(a.v,b.v);
    return a.p+a.v*t;
}
//要求闭合。
double halfplane(Line *l,int n,Line *h,Point *p){
    sort(l+1,l+n+1); int m,f=1,t=1;
    h[1]=l[1];
    for(int i=2;i<=n;++i){
        while(f<t&&!Left(p[t-1],l[i])) --t;
        while(f<t&&!Left(p[f],l[i])) ++f;
        if(fabs(Cross(h[t].v,l[i].v))<eps) h[t]=Left(h[t].p,l[i])?h[t]:l[i];
        else h[++t]=l[i];
        if(f<t) p[t-1]=intersection(h[t-1],h[t]);
    }
    while(f<t&&!Left(p[t-1],h[f])) --t;
    p[t]=intersection(h[f],h[t]);
    if(t-f<=1) return 0;
    double rs=0;
    for(int i=f;i<t;++i)
        rs+=Cross(p[i],p[i+1]);
    rs+=Cross(p[t],p[f]);
    return rs/2;
}
Point p[N]; Line l[N],hp[N];
int n,m,tot;
int main(){
    scanf("%d",&m);
    while(m--){
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%lf %lf",&p[i].x,&p[i].y);
        for(int i=1;i<=n;++i)
            l[++tot]=Line(p[i-1],p[i%n]-p[i-1]);
    }
    printf("%.3lf\n",halfplane(l,tot,hp,p));
}

/*
3
4
0 0
3 0
3 1
0 1
4
4 0
5 0
5 1
4 1
3
0 0
4 0
0 2
*/

实际上这个情况应该是没有交的,面积应该是0吧。

2020/8/30 16:44
加载中...