半平面交学习笔记

半平面交的具体过程原理再次不再过多赘述，只是整理一些细节。

1、设置边界，为了防止边界出锅，我们需要框一个大框，具体长这样。

    b[++tot]=node(-inf,inf,-inf,-inf);b[++tot]=node(-inf,-inf,inf,-inf);
    b[++tot]=node(inf,-inf,inf,inf);b[++tot]=node(inf,inf,-inf,inf);

2、把每条线段构造出来，然后用atan2算出线段与x轴的夹角。

    for(int i=1;i<=tot;++i)b[i].ang=atan2(b[i].y.y-b[i].x.y,b[i].y.x-b[i].x.x);

3、将所有线段按照夹角排序，如果夹角相等就看哪条线段更靠里，这个可以用叉积算。

bool operator <(const node &b)const{
        if(fabs(ang-b.ang)<eps)return (y-x)*(b.x-x)<eps; 
        else return ang<b.ang;
    }

4、这个非常关键，如果有平行的线段在后面算的时候会出锅，所以我们要去重，因为我们排过序了，所以我们直接保留相同夹角的第一条线段就好了。

    for(int i=1;i<=tot;++i)if(fabs(b[i].ang-b[i-1].ang)>eps)c[++top]=b[i];
    for(int i=1;i<=top;++i)b[i]=c[i];tot=top;

5、加入每条线段，维护单调队列。

    h=1;t=2;q[h]=b[1];q[t]=b[2];p[h]=jiao(b[1],b[2]);
    for(int i=3;i<=tot;++i){
        while(h<t&&left(b[i],p[t-1]))t--;
        while(h<t&&left(b[i],p[h]))h++;
        q[++t]=b[i];p[t-1]=jiao(q[t],q[t-1]);
    }
    while(h<t&&left(q[t],p[h]))h++;
    while(h<t&&left(q[h],p[t-1]))t--;

6、维护时我们要判断一条线段是否在点的左边，这个可以用叉积算。

inline bool left(node b,P a){return (a-b.x)*(b.y-b.x)>eps;}

7、我们开需要求出两条线段的交点，这个用面积(还是叉积)算。

inline point jiao(line a,line b){return b.a+(b.b-b.a)*(((b.a-a.a)*(a.b-a.a))/((a.b-a.a)*(b.b-b.a)));}

8、最后我们用叉积算出多边形的面积

    for(int i=h+2;i<=t;++i)ans+=(p[i]-p[h])*(p[i-1]-p[h])/2;

HNOI2003多边形

一开始以为要先极角排序一下，然后WA到死。

发现点是按顺序给的。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm> 
#define double double
#define N 2002
#define inf 2e9
using namespace std;
int n,top,tot,h,t;
double ans;
const double eps=1e-9;
struct point{
    double x,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};}
    double operator *(const point &b)const{return x*b.y-y*b.x;}
    point operator *(const double &b)const{return point{x*b,y*b};}
}d[N],p[N];
inline double dis(point a,point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct line{
   point a,b;double ang;
   line(){}
   line(double aa,double bb,double cc,double dd){a.x=aa;a.y=bb;b.x=cc;b.y=dd;}
   bool operator <(const line &x)const{
      if(fabs(ang-x.ang)<eps)return (b-a)*(x.a-a)<eps;
      else return ang<x.ang;
   }
}l[N],c[N],q[N];
inline bool cmp(point a,point b){
    double cj=(a-d[1])*(b-d[1]);
    return (cj>0)||(fabs(cj)<eps&&dis(a,d[1])<dis(b,d[1])); 
}
inline bool left(line a,point b){return (b-a.a)*(a.b-a.a)>eps;}
inline point jiao(line a,line b){return b.a+(b.b-b.a)*(((b.a-a.a)*(a.b-a.a))/((a.b-a.a)*(b.b-b.a)));}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lf%lf",&d[i].x,&d[i].y);
/*    int ji=1;
    for(int i=2;i<=n;++i)if(d[i].x<d[ji].x||(d[i].x==d[ji].x&&d[i].y<d[ji].y))ji=i;
    swap(d[ji],d[1]);
    sort(d+2,d+n+1,cmp);*/
    reverse(d+1,d+n+1);
    for(int i=2;i<=n;++i)l[i-1]=line(d[i-1].x,d[i-1].y,d[i].x,d[i].y);
    l[n]=line(d[n].x,d[n].y,d[1].x,d[1].y);tot=n;
    l[++tot]=line(-inf,inf,-inf,-inf);l[++tot]=line(-inf,-inf,inf,-inf);
    l[++tot]=line(inf,-inf,inf,inf);l[++tot]=line(inf,inf,-inf,inf);
    for(int i=1;i<=tot;++i)l[i].ang=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
    sort(l+1,l+tot+1);
    for(int i=1;i<=tot;++i)if(fabs(l[i].ang-l[i-1].ang)>eps)c[++top]=l[i];
    for(int i=1;i<=top;++i)l[i]=c[i];tot=top;
    h=1;t=2;q[h]=l[1];q[t]=l[2];p[1]=jiao(q[1],q[2]);
    for(int i=3;i<=tot;++i){
        while(h<t&&left(l[i],p[t-1]))t--;
        while(h<t&&left(l[i],p[h]))h++;
        q[++t]=l[i];p[t-1]=jiao(q[t],q[t-1]); 
    }
    while(h<t&&left(q[t],p[h]))h++;
    while(h<t&&left(q[h],p[t-1]))t--;//
    p[t]=jiao(q[h],q[t]);
    for(int i=h+2;i<=t;++i)ans+=(p[i]-p[h])*(p[i-1]-p[h])/2;
    ans=fabs(ans);
    printf("%.2lf",ans);
    return 0;
}
View Code

CQOI2006凸多边形

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 10002
#define inf 2e9
#define double long double
using namespace std;
const double eps=1e-9;
int n,tot,h,t,m,top;
double x[N],y[N],ans;
inline int rd(){
    int x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
struct P{
    double x,y;
    P operator +(const P &b)const{return P{x+b.x,y+b.y};}
    P operator -(const P &b)const{return P{x-b.x,y-b.y};}
    double operator *(const P &b)const{return x*b.y-y*b.x;}
    P operator *(const double &b)const{return P{x*b,y*b};}
    double operator ^(const P &b)const{return x*b.x+y*b.y;}
    inline void print(){
        cout<<x<<" "<<y<<endl;
    }
}p[N];
struct node{
    P x,y;double ang;
    node(){}
    node(int a,int b,int c,int d){x.x=a;x.y=b;y.x=c;y.y=d;ang=0;}
    bool operator <(const node &b)const{
        if(fabs(ang-b.ang)<eps)return (y-x)*(b.x-x)<eps; 
        else return ang<b.ang;
    }
    inline void print(){
        cout<<x.x<<" "<<x.y<<" "<<y.x<<" "<<y.y<<endl;
    }
}b[N],q[N],c[N];
inline P jiao(node a,node b){
    double k=((b.x-a.x)*(a.y-a.x))/((a.y-a.x)*(b.y-b.x));
    return b.x+(b.y-b.x)*k;
} 
inline bool left(node b,P a){return (a-b.x)*(b.y-b.x)>eps;}
int main(){
    n=rd();
    b[++tot]=node(-inf,inf,-inf,-inf);b[++tot]=node(-inf,-inf,inf,-inf);
    b[++tot]=node(inf,-inf,inf,inf);b[++tot]=node(inf,inf,-inf,inf);
    for(int i=1;i<=n;++i){
        m=rd();
        x[1]=rd();y[1]=rd();
        for(int j=2;j<=m;++j){
            x[j]=rd();y[j]=rd();
            b[++tot]=node(x[j-1],y[j-1],x[j],y[j]);
        }
        b[++tot]=node(x[m],y[m],x[1],y[1]);
    }
    for(int i=1;i<=tot;++i)b[i].ang=atan2(b[i].y.y-b[i].x.y,b[i].y.x-b[i].x.x);
    sort(b+1,b+tot+1);
    for(int i=1;i<=tot;++i)if(fabs(b[i].ang-b[i-1].ang)>eps)c[++top]=b[i];
    for(int i=1;i<=top;++i)b[i]=c[i];tot=top;
    h=1;t=2;q[h]=b[1];q[t]=b[2];p[h]=jiao(b[1],b[2]);
    for(int i=1;i<=tot;++i){
        while(h<t&&left(b[i],p[t-1]))t--;
        while(h<t&&left(b[i],p[h]))h++;
        q[++t]=b[i];p[t-1]=jiao(q[t],q[t-1]);
    }
    while(h<t&&left(q[t],p[h]))h++;
    while(h<t&&left(q[h],p[t-1]))t--;
    if(t-h+1<=2){printf("0.000
");return 0;}
    p[t]=jiao(q[h],q[t]);
    for(int i=h+2;i<=t;++i)ans+=(p[i]-p[h])*(p[i-1]-p[h])/2;
    ans=fabs(ans);
    printf("%.3LF",ans);
    return 0;
}
View Code

HNOI2012射箭

瞎**化简一下二次函数，发现这就是半平面交，外面套个二分答案就可以了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define inf 1e14 
#define N 220002
#define double long double
using namespace std;
typedef long long ll;
int tot,n;
const double eps=1e-14;
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x; 
}
struct node{double x,y1,y2;};
struct point{
    double x,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};}
    double operator *(const point &b)const{return x*b.y-y*b.x;}
    point operator *(const double &b)const{return point{x*b,y*b};}
}p[N];
struct line{
    point a,b;double ang;int id;
    line(){id=0;} 
    line(double x1,double x2,double x3,double x4){a.x=x1;a.y=x2;b.x=x3;b.y=x4;id=ang=0;} 
    bool operator <(const line &x)const{
        if(ang==x.ang)return (b-a)*(x.a-a)>eps;
        return ang<x.ang;
    }
}l[N],a[N],q[N];
inline point jiao(line a,line b){//?????
    double k=((a.b-a.a)*(b.a-a.a))/((b.b-b.a)*(a.b-a.a));
    return b.a+(b.b-b.a)*k;
}
bool left(point x,line b){return (x-b.a)*(b.b-b.a)>eps;}
inline bool check(int mid){
    int top=0;
    for(int i=1;i<=tot;++i)if(l[i].id<=mid)if(!top||fabs(l[i].ang-a[top].ang)>eps)a[++top]=l[i];
    int h=1,t=2;q[1]=a[1];q[2]=a[2];p[1]=jiao(a[1],a[2]);
    for(int i=3;i<=top;++i){
        while(h<t&&left(p[t-1],a[i]))t--;
        while(h<t&&left(p[h],a[i]))h++;
        q[++t]=a[i];p[t-1]=jiao(q[t-1],q[t]);
    } 
    while(h<t&&left(p[t-1],q[h]))t--;
    while(h<t&&left(p[h],q[t]))h++;
    //cout<<mid<<" "<<h<<" "<<t<<endl;
    return t-h>=2;
}
int main(){
    n=rd();double x,y1,y2;
    l[++tot]=line(-inf,inf,-inf,-inf);l[++tot]=line(-inf,-inf,inf,-inf);
    l[++tot]=line(inf,-inf,inf,inf);l[++tot]=line(inf,inf,-inf,inf);
    for(int i=1;i<=n;++i){
        x=rd();y1=rd();y2=rd();
        l[++tot].a.x=-1;l[tot].a.y=y1/x+x;
        l[tot].b.x=1;l[tot].b.y=y1/x-x;l[tot].id=i;
        l[++tot].a.x=1;l[tot].a.y=y2/x-x;
        l[tot].b.x=-1;l[tot].b.y=y2/x+x;l[tot].id=i;
    }
    for(int i=1;i<=tot;++i)l[i].ang=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
    sort(l+1,l+tot+1);
    int l=0,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){ans=mid;l=mid+1;} 
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ZH-comld/p/10170902.html