首页 > 代码库 > 计算几何-poj2451-HPI
计算几何-poj2451-HPI
This article is made by Jason-Cow.
Welcome to reprint.
But please post the article‘s address.
题意,求半平面交,并且保证有解
poj2451
给张图边界(|x,y|<=1000,题目为1e4)
别问我为什么TLE
我当成多组处理没有判断文末符号,加上就!A!啦!
直接上模板
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <cmath> 8 #include <queue> 9 #include <map> 10 #include <set> 11 using namespace std; 12 #define sqr(x) ((x)*(x)) 13 #define RG register 14 #define op operator 15 #define IL inline 16 typedef double db; 17 typedef bool bl; 18 const db pi=acos(-1.0),eps=1e-10; 19 struct D{ 20 db x,y; 21 D(db x=0.0,db y=0.0):x(x),y(y){} 22 }; 23 typedef D V; 24 bl operator<(D A,D B){return A.x<B.x||(A.x==B.x&&A.y<B.y);} 25 V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);} 26 V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);} 27 V operator*(V A,db N){return V(A.x*N,A.y*N);} 28 V operator/(V A,db N){return V(A.x/N,A.y/N);} 29 30 db Ang(db x){return(x*180.0/pi);} 31 db Rad(db x){return(x*pi/180.0);} 32 V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));} 33 db Dis(D A,D B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));} 34 db Cross(V A,V B){return A.x*B.y-A.y*B.x;} 35 36 db Area(D*R,int n){ 37 db S=0.0; 38 for(int i=1;i<n;i++)S+=Cross(R[i]-R[1],R[i+1]-R[1]); 39 return S/2; 40 } 41 42 db Length(D*R,int n){ 43 db C=0.0; 44 for(int i=2;i<=n;i++)C+=Dis(R[i],R[i-1]); 45 return C+Dis(R[n],R[1]); 46 } 47 48 struct L{ 49 D P,v; 50 db a; 51 L(){} 52 L(D P,V v):P(P),v(v){a=atan2(v.y,v.x);} 53 bool operator<(const L x)const{return a<x.a;} 54 }; 55 56 D Intersect(L a,L b){ 57 V u=a.P-b.P; 58 return a.P+a.v*(Cross(b.v,u)/Cross(a.v,b.v)); 59 } 60 61 bool Left(L l,D A){ 62 return Cross(l.v,A-l.P)>0; 63 } 64 65 int HPI(L*l,int n,D*ans){ 66 int head,tail,m=0; 67 D*P=new D[n];L*q=new L[n]; 68 sort(l+1,l+n+1),q[head=tail=0]=l[1]; 69 for(int i=2;i<=n;i++){ 70 while(head<tail && !Left(l[i],P[tail-1]))tail--; 71 while(head<tail && !Left(l[i],P[head])) head++; 72 q[++tail]=l[i]; 73 if(fabs(Cross(q[tail].v,q[tail-1].v))<eps){ 74 tail--; 75 if(Left(q[tail],l[i].P))q[tail]=l[i]; 76 } 77 if(head<tail)P[tail-1]=Intersect(q[tail-1],q[tail]); 78 } 79 while(head<tail && !Left(q[head],P[tail-1]))tail--; 80 if(tail-head<=1)return 0; 81 P[tail]=Intersect(q[tail],q[head]); 82 for(int i=head;i<=tail;i++)ans[++m]=P[i]; 83 return m; 84 } 85 86 const int maxn=2e4+10; 87 L l[maxn];D A[maxn]; 88 int main(){ 89 D LU(0,1e4),LD(0,0),RD(1e4,0),RU(1e4,1e4); 90 for(int n;scanf("%d",&n)!=EOF;){ 91 for(int i=1;i<=n;i++){ 92 db a,b,c,d; 93 scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 94 D A(a,b),B(c,d); 95 l[i]=L(A,B-A); 96 } 97 l[++n]=L(LU,V(0,-1)); 98 l[++n]=L(LD,V(1,0)); 99 l[++n]=L(RD,V(0,1)); 100 l[++n]=L(RU,V(-1,0)); 101 int m=HPI(l,n,A); 102 printf("%.1lf\n",Area(A,m)); 103 } 104 return 0; 105 }
计算几何-poj2451-HPI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。