bzoj4445(半平面交)

列出式子对一下然后上半平面交

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200010;
const double eps=1e-12;
int n,m;
int head,tail;
struct vec{
    double x,y;
    vec(double x=0,double y=0):x(x),y(y){}
    vec operator-(vec& a){
        return vec(x-a.x,y-a.y);
    }
    vec operator+(vec&a){
        return vec(x+a.x,y+a.y);
    }
}po[maxn],g[maxn],tmp;
vec operator*(vec a,double t){return vec(a.x*t,a.y*t);}
double cross(vec a,vec b){return a.x*b.y-b.x*a.y;}
struct lin{
    vec p,v;
    double ang;
    lin(){}
    lin(vec p,vec v):p(p),v(v){ang=atan2(v.y,v.x);}
    bool operator<(const lin&a)const{
        return ang<a.ang;
    }
}ll[maxn],q[maxn];
bool onl(lin L,vec p){
    return cross(L.v,p-L.p)>0;
}
vec qj(lin a,lin b){
    vec u=a.p-b.p;
    double t=cross(b.v,u)/cross(a.v,b.v);
    return a.v*t+a.p;
}
int halfj(){
    sort(ll,ll+n);
    //int head,tail;
    q[head=tail=0]=ll[0];
    for(int i=1;i<n;++i){
        while(head<tail&&!onl(ll[i],g[tail-1]))tail--;
        while(head<tail&&!onl(ll[i],g[head]))head++;
        q[++tail]=ll[i];
        if(fabs(cross(q[tail].v,q[tail-1].v))<eps){
            --tail;if(onl(q[tail],ll[i].p))q[tail]=ll[i];
        }
        if(head<tail)g[tail-1]=qj(q[tail-1],q[tail]);
    }
    while(head<tail&&!onl(q[head],g[tail-1]))--tail;
    g[tail]=qj(q[head],q[tail]);++tail;
}/*
void halfj(){
    sort(ll,ll+n);
    //for(int i=0;i<n;++i)cout<<ll[i].p.x<<' '<<ll[i].p.y<<' '<<ll[i].v.x<<' '<<ll[i].v.y<<endl;
    q[head=tail=0]=ll[0];
    for(int i=1;i<n;++i){
        while(head<tail&&!onl(ll[i],g[tail-1]))tail--;
        while(head<tail&&!onl(ll[i],g[head]))head++;
        q[++tail]=ll[i];
        if(fabs(cross(q[tail].v,q[tail-1].v))<eps){
            --tail;if(onl(q[tail],ll[i].p))q[tail]=ll[i];
        }
        if(head<tail)g[tail-1]=qj(q[tail-1],q[tail]);
    }
    while(head<tail&&!onl(q[head],g[tail-1]))--tail;
}*/
void add(int i,int j){
    double a=po[0].y-po[i].y-po[1].y+po[j].y;
    double b=po[1].x-po[j].x-po[0].x+po[i].x;
    double c=cross(po[0],po[1])-cross(po[i],po[j]);
    tmp.x=b?0:-c/a;
    tmp.y=b?-c/b:0;
    ll[i]=lin(tmp,vec(-b,a));
}
double are(vec *p,int n){
    double sum=cross(p[n-1],p[0]);
    for(int i=1;i<n;++i){
        sum+=cross(p[i-1],p[i]);
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&po[i].x,&po[i].y);
    }
    ll[0]=lin(po[0],po[1]-po[0]);
    for(int i=1;i<n;++i)add(i,(i+1)%n);
    halfj();
    printf("%.4lf
",are(g,tail)/are(po,n));
    return 0;
}
/*
1 8 -1 -1
0 7 1 -6
0 0.777778 9 1
0 -57 1 9
0 8.16667 -6 1
*/