LG4196 [CQOI2006]凸多边形

佚名 5年前 (2019-04-13) 随笔 1689人围观抢沙发百度已收录

题意

题目描述

逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：

则相交部分的面积为5.233。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入输出格式

输入格式：

第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。

输出格式：

输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

5.233

说明

100%的数据满足：2<=n<=10，3<=mi<=50，每维坐标为[-1000,1000]内的整数

分析

这题数据范围这么小，直接上半平面交模板即可。

点->左闭右开区间，半平面->闭区间。

操作顺序：

弹双端队列
加入队列
判平行
求交点

最后还要用第一个半平面去除无用的平面。当last-first<=1时，半平面交是空集

时间复杂度\(O(n\log n)\)

代码

注意空集的时候面积输出0仍然要保留三位小数。

算面积的写错了仍然能AC？

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define co const
using namespace std;

co double eps=1e-8;
int dcmp(double x) {return fabs(x)<eps?0:(x>0?1:-1);}
typedef struct Point{double x,y;}Vector;
Vector operator+(co Vector&u,co Vector&v) {return (Vector){u.x+v.x,u.y+v.y};}
Vector operator-(co Vector&u,co Vector&v) {return (Vector){u.x-v.x,u.y-v.y};}
Vector operator*(co Vector&u,double k) {return (Vector){u.x*k,u.y*k};}
double cross(co Vector&u,co Vector&v) {return u.x*v.y-u.y*v.x;}
double dot(co Vector&u,co Vector&v) {return u.x*v.x+u.y*v.y;}
struct Line{
    Point p;Vector v;
    double ang;
    bool operator<(co Line&l) {return ang<l.ang;}
};
bool left(co Line&l,co Point&p){
    return dcmp(cross(l.v,p-l.p))>0;
}
Point intersection(co Line&a,co Line&b){
    return a.p+a.v*(cross(b.v,a.p-b.p)/cross(a.v,b.v));
}

int main(){
    int n;scanf("%d",&n);
    vector<Line>ls;
    for(int m;n--;){
        scanf("%d",&m);
        static Point p[50];
        for(int i=0;i<m;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=0;i<m;++i) ls.push_back((Line){p[i],p[(i+1)%m]-p[i]});
    }
    for(int i=0;i<ls.size();++i) ls[i].ang=atan2(ls[i].v.y,ls[i].v.x);
    sort(ls.begin(),ls.end());
    vector<Point> p(ls.size());
    vector<Line> q(ls.size());
    int first,last;
    q[first=last=0]=ls[0];
    for(int i=1;i<ls.size();++i){
        while(first<last&&!left(ls[i],p[last-1])) --last;
        while(first<last&&!left(ls[i],p[first])) ++first;
        q[++last]=ls[i];
        if(dcmp(cross(q[last].v,q[last-1].v))==0){
            --last;
            if(left(q[last],ls[i].p)) q[last]=ls[i];
        }
        if(first<last) p[last-1]=intersection(q[last-1],q[last]);
    }
    while(first<last&&!left(q[first],p[last-1])) --last;
    if(last-first<=1) return puts("0.000"),0;
    p[last]=intersection(q[last],q[first]);
    vector<Point> ans;
    for(int i=first;i<=last;++i) ans.push_back(p[i]);
    double area=0;
    for(int i=1;i<ans.size();++i) area+=cross(ans[i]-ans[0],ans[(i+1)%ans.size()]-ans[0]);
    printf("%.3lf",fabs(area/2));
    return 0;
}