bzoj 2618: [Cqoi2006]凸多边形半平面交

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2618

半平面交板子题

#include<bits/stdc++.h>

#define db double
#define maxn 505
#define eps 1e-7
#define Vector point

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct point{
    db x,y;
    point(db xx=0,db yy=0){x=xx,y=yy;}
    friend point operator + (Vector a,Vector b){return point(a.x+b.x,a.y+b.y);}
    friend point operator - (Vector a,Vector b){return point(a.x-b.x,a.y-b.y);}
    friend point operator * (Vector a,db b){return point(a.x*b,a.y*b);}
    friend point operator / (Vector a,db b){return point(a.x/b,a.y/b);}
    friend bool operator < (Vector a,Vector b){return a.x<b.x || fabs(a.x-b.x)<eps && a.y<b.y;}
}p[maxn],a[maxn];

struct line{
    point p,v;
    db ang;
    line(){}
    line(point P,Vector V){
        p=P;
        v=V;
        ang=atan2(v.y,v.x);
    }
    friend bool operator < (line a,line b){
        return a.ang<b.ang;
    }
}L[maxn],q[maxn];

inline db cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

inline point GetPoint(line a,line b){
    Vector V=a.p-b.p;
    db t=cross(b.v,V)/cross(a.v,b.v);
    return a.p+a.v*t;
}

inline bool Onleft(line l,point p){
    return cross(l.v,p-l.p)>0;
}

int cnt;

inline void init(){
    int T=rd();
    while(T--){
        int n=rd();
        for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd();
        p[n+1]=p[1];
        for(int i=1; i<=n; i++)L[++cnt]=line(p[i],p[i+1]-p[i]);
    }
}

int head=1,tail=0;

inline void hpi(){
    sort(L+1,L+cnt+1);
    q[++tail]=L[1];
    for(int i=2; i<=cnt; i++){
        while(head<tail && !Onleft(L[i],p[tail-1]))tail--;
        while(head<tail && !Onleft(L[i],p[head]))head++;
        q[++tail]=L[i];
        if(fabs(cross(q[tail].v,q[tail-1].v))<eps){
            tail--;
            if(Onleft(q[tail],L[i].p))q[tail]=L[i];
        }
        if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);
    }
    while(head<tail && !Onleft(q[head],p[tail-1]))tail--;
    p[tail]=GetPoint(q[tail],q[head]);
}

inline void work(){
    hpi();
    db ans=0;
    for(int i=head+1; i<tail; i++){
        ans+=cross(p[i]-p[head],p[i+1]-p[head]);
    }
    printf("%.3lf\n",ans*0.5);
}

int main(){
    init();
    work();
    
    return 0;
}

#include<bits/stdc++.h>

#define db double

#define maxn 505

#define eps 1e-7

#define Vector point

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct point{

db x,y;

point(db xx=0,db yy=0){x=xx,y=yy;}

friend point operator + (Vector a,Vector b){return point(a.x+b.x,a.y+b.y);}

friend point operator - (Vector a,Vector b){return point(a.x-b.x,a.y-b.y);}

friend point operator * (Vector a,db b){return point(a.x*b,a.y*b);}

friend point operator / (Vector a,db b){return point(a.x/b,a.y/b);}

friend bool operator < (Vector a,Vector b){return a.x<b.x || fabs(a.x-b.x)<eps && a.y<b.y;}

}p[maxn],a[maxn];

struct line{

point p,v;

db ang;

line(){}

line(point P,Vector V){

p=P;

v=V;

ang=atan2(v.y,v.x);

}

friend bool operator < (line a,line b){

return a.ang<b.ang;

}

}L[maxn],q[maxn];

inline db cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

inline point GetPoint(line a,line b){

Vector V=a.p-b.p;

db t=cross(b.v,V)/cross(a.v,b.v);

return a.p+a.v*t;

}

inline bool Onleft(line l,point p){

return cross(l.v,p-l.p)>0;

}

int cnt;

inline void init(){

int T=rd();

while(T--){

int n=rd();

for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd();

p[n+1]=p[1];

for(int i=1; i<=n; i++)L[++cnt]=line(p[i],p[i+1]-p[i]);

}

int head=1,tail=0;

inline void hpi(){

sort(L+1,L+cnt+1);

q[++tail]=L[1];

for(int i=2; i<=cnt; i++){

while(head<tail && !Onleft(L[i],p[tail-1]))tail--;

while(head<tail && !Onleft(L[i],p[head]))head++;

q[++tail]=L[i];

if(fabs(cross(q[tail].v,q[tail-1].v))<eps){

tail--;

if(Onleft(q[tail],L[i].p))q[tail]=L[i];

}

if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);

}

while(head<tail && !Onleft(q[head],p[tail-1]))tail--;

p[tail]=GetPoint(q[tail],q[head]);

}

inline void work(){

hpi();

db ans=0;

for(int i=head+1; i<tail; i++){

ans+=cross(p[i]-p[head],p[i+1]-p[head]);

}

printf("%.3lf\n",ans*0.5);

}

int main(){

init();

work();

return 0;

}

everlasting

bzoj 2618: [Cqoi2006]凸多边形半平面交

赞过：

相关

《bzoj 2618: [Cqoi2006]凸多边形半平面交》有1个想法

发表评论取消回复

共享此文章：

赞过：

相关

《bzoj 2618: [Cqoi2006]凸多边形 半平面交》有1个想法

发表评论 取消回复

《bzoj 2618: [Cqoi2006]凸多边形半平面交》有1个想法

发表评论取消回复