G54 半平面交 双端队列【计算几何】

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-12;
const int N=2e4+10;

struct Point
{
    double x,y;
    Point(){}
    Point(double a,double b):x(a),y(b){}
    void input(){scanf("%lf%lf",&x,&y);} 
    friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
    friend bool cmpy(Point a, Point b){return a.y!=b.y?a.y<b.y:a.x<b.x;}
    friend Point operator+(Point a,Point b){ return {a.x+b.x,a.y+b.y};}
    friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};}
    friend Point operator*(Point a, double t){return {a.x*t,a.y*t};}
    friend Point operator/(Point a, double t){return {a.x/t,a.y/t};}
    friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;}
}P[N];
struct Line
{
    Point a,b;
    Line(){}
    Line(Point x,Point y):a(x),b(y){}
    friend double angle(Line L) {return atan2(L.b.y-L.a.y, L.b.x-L.a.x);}
    friend bool operator<(Line L1, Line L2)
    {
        double A=angle(L1), B=angle(L2);
        return fabs(A-B)>eps ? A<B : det(L1.b-L1.a,L2.b-L1.a)<0;//如果平行，L1在L2的左边 
    }
    friend Point Line_make_Point(Line L1,Line L2)
    {
        Point a=L1.a,b=L1.b,c=L2.a,d=L2.b;
        double s1=det(c-a,b-a);
        double s2=det(d-a,b-a);
        return (c*s2-d*s1)/(s2-s1);
    }
    friend bool Left(Line L,Point p)
    {
        return det(L.b-L.a,p-L.a)>0;
    }
}L[N],q[N];int n;

double half_plane()
{
    sort(L+1,L+n+1);
    int h=1,t=1;q[1]=L[1];
    for(int i=2; i<=n; i++)
    {
        if(angle(L[i])-angle(L[i-1])<eps) continue;
        while( h<t && !Left( L[i],Line_make_Point(q[t],q[t-1]) ) )t--;
        while( h<t && !Left( L[i],Line_make_Point(q[h],q[h+1]) ) )h++;
        q[++t]=L[i];
    }
        while( h<t && !Left( q[h],Line_make_Point(q[t],q[t-1]) ) )t--;

    q[++t]=q[h]; //封口
    
    double res=0;int k=0;
    for(int i=h; i<t; i++)P[++k]=Line_make_Point(q[i],q[i+1]);
    for(int i=2; i<k; i++)res+=det(P[i]-P[1],P[i+1]-P[1]);
    return res/2; //面积
}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)L[i].a.input(),L[i].b.input();
    printf("%.1lf\n", half_plane());
    return 0;
}

G54 半平面交 双端队列【计算几何】

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-12;
const int N=2e4+10;

struct Point
{
	double x,y;
	Point(){}
	Point(double a,double b):x(a),y(b){}
	void input(){scanf("%lf%lf",&x,&y);} 
	friend bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
	friend bool cmpy(Point a, Point b){return a.y!=b.y?a.y<b.y:a.x<b.x;}
	friend Point operator+(Point a,Point b){ return {a.x+b.x,a.y+b.y};}
	friend Point operator-(Point a,Point b){ return {a.x-b.x,a.y-b.y};}
	friend Point operator*(Point a, double t){return {a.x*t, a.y*t};}
	friend Point operator/(Point a, double t){return {a.x/t, a.y/t};}
	friend double det(Point a,Point b){return a.x*b.y-a.y*b.x;}
}P[N];
struct Line
{
	Point a,b;
	Line(){}
	Line(Point x,Point y):a(x),b(y){}
	friend double angle(Line L) {return atan2(L.b.y-L.a.y, L.b.x-L.a.x);}
	friend bool operator<(Line L1, Line L2)
	{
		double A=angle(L1), B=angle(L2);
		return fabs(A-B)>eps ? A<B : det(L1.b-L1.a,L2.b-L1.a)<0;//如果平行，L1在L2的左边 
	}
	friend Point Line_make_Point(Line L1,Line L2)
	{
		Point a=L1.a,b=L1.b,c=L2.a,d=L2.b;
		double s1=det(c-a,b-a);
		double s2=det(d-a,b-a);
		return (c*s2-d*s1)/(s2-s1);
	}
	friend bool Left(Line L,Point p)
	{
		return det(L.b-L.a,p-L.a)>0;
	}
}L[N],q[N];int n;

double half_plane()
{
	sort(L+1,L+n+1);
	int h=1,t=1;q[1]=L[1];
	for(int i=2; i<=n; i++)
	{
		if(angle(L[i])-angle(L[i-1])<eps) continue;
		while( h<t && !Left( L[i],Line_make_Point(q[t],q[t-1]) ) )t--;
		while( h<t && !Left( L[i],Line_make_Point(q[h],q[h+1]) ) )h++;
		q[++t]=L[i];
	}
	    while( h<t && !Left( q[h],Line_make_Point(q[t],q[t-1]) ) )t--;

	q[++t]=q[h]; //封口
	
	double res=0;int k=0;
	for(int i=h; i<t; i++)P[++k]=Line_make_Point(q[i],q[i+1]);
	for(int i=2; i<k; i++)res+=det(P[i]-P[1],P[i+1]-P[1]);
	return res/2; //面积
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)L[i].a.input(),L[i].b.input();
	printf("%.1lf\n", half_plane());
	return 0;
}