| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用Zzy方法(nlog(n))过,注意eps至少要去1e-10/*
题意:给出一些向量,求出围成的多边形的核的面积
朱泽圆专为他那篇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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator