首页 > 代码库 > [poj2451]Uyuw's Concert
[poj2451]Uyuw's Concert
半平面交滴裸题,但是要求nlogn,练练手
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define MN 50000 #define eps 1e-17 #define ld long double using namespace std; inline int read() { 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 P { ld x,y; P(ld _x=0,ld _y=0):x(_x),y(_y){} P operator +(P b){return P(x+b.x,y+b.y);} P operator -(P b){return P(x-b.x,y-b.y);} P operator *(ld b){return P(x*b,y*b);} ld operator^(P b){return x*b.y-b.x*y;} }p[MN+5]; struct L { P p,v;ld slop; L(){} L(P x,P y):p(x),v(y){slop=atan2(y.y,y.x);} P operator *(L y){P b=p-y.p;ld t=(y.v^b)/(v^y.v);return p+v*t;} bool operator <(const L&y)const{return slop<y.slop;} bool left(P y){return (v^(y-p))>eps;} }q[MN+5],s[MN+5]; int n,top,tail; void solve() { q[top=tail=1]=s[1]; for(int i=2;i<=n;i++) { while(top>tail&&!s[i].left(p[top])) --top; while(top>tail&&!s[i].left(p[tail+1])) ++tail; if(fabs(s[i].slop-q[top].slop)<eps) q[top]=s[i].left(q[top].p)?q[top]:s[i]; else q[++top]=s[i]; p[top]=q[top]*q[top-1]; } while(top>tail&&!q[tail].left(p[top])) --top; } int main() { n=read(); for(int i=1;i<=n;i++) { double x,y,x2,y2;scanf("%lf%lf%lf%lf",&x,&y,&x2,&y2); s[i]=L(P(x,y),P(x2-x,y2-y)); } s[++n]=L(P(0,0),P(10000,0)); s[++n]=L(P(10000,0),P(0,10000)); s[++n]=L(P(10000,10000),P(-10000,0)); s[++n]=L(P(0,10000),P(0,-10000)); sort(s+1,s+n+1); solve();p[tail]=q[top]*q[tail]; if(top-tail<2) return 0*puts("0.0"); ld ans=p[top]^p[tail]; for(int i=tail;i<top;i++) ans+=p[i]^p[i+1]; printf("%.1lf\n",(double)fabs(ans)/2.0); return 0; }
[poj2451]Uyuw's Concert
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。