Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用Zzy方法(nlog(n))过,注意eps至少要去1e-10

Posted by ecjtu_yuweiwei at 2014-07-28 19:57:42 on Problem 2451
/*
题意:给出一些向量,求出围成的多边形的核的面积
朱泽圆专为他那篇nlog(n)算法解决半平面交问题的论文而出的题目,至今不会自己写(汗颜,自己全是套模板).
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int Max=20001;
using namespace std;
struct point
{
    double x;
    double y;
}p[Max];
struct Segment
{
    point s;
    point e;
    double angle;
    void get_angle()
    {
        angle=atan2(e.y-s.y,e.x-s.x);//得到斜率对应的角度
    }
}seg[Max];
int m;
//叉积为正说明,p2在p0-p1的左侧
double xmul(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point Get_Intersect(Segment s1,Segment s2)//求交点
{
    double u,v;
    u=xmul(s1.s,s1.e,s2.s);
    v=xmul(s1.e,s1.s,s2.e);
    point res;
    res.x=(s2.s.x*v+s2.e.x*u)/(u+v);
    res.y=(s2.s.y*v+s2.e.y*u)/(u+v);
    return res;
}
bool cmp(Segment s1,Segment s2)
{

    if(s1.angle>s2.angle) //先按极角排序
        return true;
    else if(zero(s1.angle-s2.angle)&&xmul(s2.s,s2.e,s1.e)>-eps) //极角相等,内侧的在前
        return true;
    return false;
}
void initial()//初始化
{
    seg[0].s.x=0;
    seg[0].s.y=0;
    seg[0].e.x=10000;
    seg[0].e.y=0;
    seg[0].get_angle();
    seg[1].s.x=10000;
    seg[1].s.y=0;
    seg[1].e.x=10000;
    seg[1].e.y=10000;
    seg[1].get_angle();
    seg[2].s.x=10000;
    seg[2].s.y=10000;
    seg[2].e.x=0;
    seg[2].e.y=10000;
    seg[2].get_angle();
    seg[3].s.x=0;
    seg[3].s.y=10000;
    seg[3].e.x=0;
    seg[3].e.y=0;
    seg[3].get_angle();
}
void HalfPlaneIntersect(Segment seg[],int n)//半平面交模版(nlog(n))
{
    sort(seg,seg+n,cmp);
    int temp=1;
    for(int i=1; i<n; i++)
    {
        if(!zero(seg[i].angle-seg[temp-1].angle))
            seg[temp++]=seg[i];
    }
    n=temp;
    Segment deq[Max];
    deq[0]=seg[0];
    deq[1]=seg[1];
    int head=0,tail=1;
    for(int i=2; i<n; i++)
    {
        while(head<tail&&xmul(seg[i].s,seg[i].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps)
            tail--;
        while(head<tail&&xmul(seg[i].s,seg[i].e,Get_Intersect(deq[head],deq[head+1]))<-eps)
            head++;
        deq[++tail]=seg[i];
    }
    while(head<tail&&xmul(deq[head].s,deq[head].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps)
        tail--;
    while(head<tail&&xmul(deq[tail].s,deq[tail].e,Get_Intersect(deq[head],deq[head+1]))<-eps)
        head++;
    if(head==tail)
        return;
    m=0;
    for(int i=head; i<tail; i++)
        p[m++]=Get_Intersect(deq[i],deq[i+1]);
    if(tail>head+1)
        p[m++]=Get_Intersect(deq[head],deq[tail]);
}
double Get_area(point p[],int &n)//叉积求多边形面积
{
    double area=0;
    for(int i=1; i<n-1; i++)
        area+=xmul(p[0],p[i],p[i+1]);
    return fabs(area)/2.0;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        initial();//初始化
        for(int i=4; i<n+4; i++)
        {
            scanf("%lf%lf%lf%lf",&seg[i].s.x,&seg[i].s.y,&seg[i].e.x,&seg[i].e.y);
            //cin>>seg[i].s.x>>seg[i].s.y>>seg[i].e.x>>seg[i].e.y;
            seg[i].get_angle();
        }
        HalfPlaneIntersect(seg,n+4);
        printf("%.1lf\n",Get_area(p,m));
        //cout<<setprecision(1)<<setiosflags(ios::fixed)<<Get_area(p,m)<<endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator