半平面交 — 模板

 

半平面交

 

题目描述

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 1510
#define db double
inline int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct mp{db x,y;}a[N],g[N];
mp operator +(mp a,mp b){return (mp){a.x+b.x,a.y+b.y};}
mp operator -(mp a,mp b){return (mp){a.x-b.x,a.y-b.y};}
db operator *(mp a,mp b){return a.x*b.y-b.x*a.y;}
mp operator *(db a,mp b){return (mp){b.x*a,b.y*a};}
struct xx{mp x,y;db af;}b[N],f[N];
bool operator <(xx a,xx b){return a.af==b.af?a.y*(b.x-a.x)<0:a.af<b.af;}
int T,n;
bool fl;
mp Q(xx a,xx b)
{
    db t=a.y*b.y;
    if(!t){puts("0.00");fl=1;}
    return (b.y*(a.x-b.x))/t*a.y+a.x;
}
void sol()
{
    fl=0;n=rd();
    for(int i=1;i<=n;i++){a[i].x=rd();a[i].y=rd();}
    reverse(a+1,a+n+1);
    a[n+1]=a[1];
    for(int i=1;i<=n;i++) b[i]=(xx){a[i],a[i+1]-a[i],atan2((a[i+1]-a[i]).y,(a[i+1]-a[i]).x)};
    sort(b+1,b+n+1);
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        if(i==1||b[i].af>b[i-1].af)
        {
            xx x=b[i];
            while(l<r&&x.y*(g[r]-x.x)<=0) r--;
            while(l<r&&x.y*(g[l+1]-x.x)<=0) l++;
            f[++r]=x;
            if(l<r) g[r]=Q(f[r-1],x);
            if(fl) return;
        }
    }
    g[l]=g[r+1]=Q(f[l],f[r]);
    if(fl) return;
    db ans=0;
    for(int i=l;i<=r;i++) ans+=g[i]*g[i+1];
    printf("%.2lf\n",abs(ans)*1.0/2);
}
int main()
{
    T=rd();
    while(T--) sol();
    return 0;
}
/*
1
7
0 0
4 4
4 7
9 7
13 -1
8 -6
4 -4
 
*/

 

评论

还没有任何评论,你来说两句吧

发表评论

衫小寨 出品