emm

Half Plane Intersection

建议背就完事了...

这里说几点：

• 先退队尾再退队首。
• 记得判下队列无解。
• 不要使用线段交点。请使用直线交点。且注意向量的方向。其中用到了正弦定理。

Code

// Code by ajcxsu
// Problem: half

#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#define eps (1e-8)
using namespace std;

const int N=2e4+10;
double rbq(double x, double y) { return fabs(x-y)<eps; }
struct P {
    double x, y, d;
    P () { x=y=d=0; }
    P (double a, double b) { x=a, y=b, d=atan2(y, x); if(d<0) d+=2.0*M_PI; }
    P operator + (P b) { return P(x+b.x, y+b.y); }
    P operator - (P b) { return P(x-b.x, y-b.y); }
    P operator * (double b) { return P(x*b, y*b); }
    double operator ^ (P b) { return x*b.y-y*b.x; }
    double norm() { return x*x+y*y; }
    double dis() { return sqrt(norm()); }
    bool operator < (const P &b) const { return d<b.d; }
    bool operator == (const P &b) const { return rbq(d, b.d); }
    bool operator != (const P &b) const { return !rbq(d, b.d); }
} ;
struct Seg {
    P s, e, b;
    Seg () { s=e=b=P(); }
    Seg (P x, P y) { s=x, e=y, b=e-s; }
} s[N], rs[N];
double side(P x, Seg s) { return s.b^(x-s.s); }
bool cmp(const Seg &a, const Seg &b) { return a.b==b.b?side(a.s, b)>0:a.b<b.b; }

double S(P a, P b) { return fabs(a^b); }

P ins(Seg a,Seg b) {
    P p1=a.s,p2=b.s,v1=a.e,v2=b.e;
    v1=v1-p1;v2=v2-p2;
    P u=p2-p1;
    P p=p2+v2*((u^v1)/(v1^v2));
    return p;
}

istream& operator >> (istream &in, P &x) {
    double a, b; in>>a>>b, x=P(a, b);
    return in;
}
ostream& operator << (ostream &out, P x) {
    return out<<x.x<<' '<<x.y;
}

int sn;
Seg qu[N]; int h, t;
double HPI() {
    int n=sn;
    sort(s+1, s+1+n, cmp);
    int p=0; rs[++p]=s[1];
    for(int i=2; i<=n; i++) if(s[i].b!=s[i-1].b)
        rs[++p]=s[i];
    qu[t++]=rs[1], qu[t++]=rs[2];
    for(int i=3; i<=p; i++) {
        while(h+1<t && side(ins(qu[t-1], qu[t-2]), rs[i])<0) t--;
        while(h+1<t && side(ins(qu[h], qu[h+1]), rs[i])<0) h++;
        qu[t++]=rs[i];
    }
    while(h+1<t && side(ins(qu[t-1], qu[t-2]), qu[h])<0) t--;
    while(h+1<t && side(ins(qu[h], qu[h+1]), qu[t-1])<0) h++;
    if(t-h<=1) return 0;
    vector<P> tmp;
    for(int j=h; j<t-1; j++)
        tmp.push_back(ins(qu[j], qu[j+1]));
    tmp.push_back(ins(qu[t-1], qu[h]));
    double area=0;
    for(int i=0, len=tmp.size(); i<len-1; i++) area+=tmp[i]^tmp[i+1];
    area+=tmp.back()^tmp.front();
    return fabs(area)/2.0;
}

P tmp[100];
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.setf(ios::fixed), cout<<setprecision(3);
    int n; cin>>n;
    for(int i=0; i<n; i++) {
        int k; cin>>k;
        for(int j=0; j<k; j++) cin>>tmp[j];
        for(int j=0; j<k-1; j++) s[++sn]=Seg(tmp[j],tmp[j+1]);
        s[++sn]=Seg(tmp[k-1],tmp[0]);
    }
    cout<<HPI()<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/half-plane-intersection.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆