题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2732
高中的线性规划知识
一个线段可以转变为两个半平面，然后二分答案，跑半平面交
注意精度问题，及其的恶心， $ long double $ 和 $ 1e-18 $ 的 $eps$ ……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include<bits/stdc++.h> #define db long double #define Vector point #define maxn 100010 #define eps 1e-18 #define inf 1e10 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ db x,y; point(db xx=0,db yy=0){x=xx,y=yy;} friend Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);} friend Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);} friend Vector operator * (Vector A,db B){return Vector(A.x*B,A.y*B);} friend Vector operator / (Vector A,db B){return Vector(A.x/B,A.y/B);} }p[maxn*2]; struct line{ int id; point p; Vector v; db ang; line(){} line(point A,Vector B,int C){ p=A; v=B; ang=atan2(B.y,B.x); id=C; } friend bool operator < (line A,line B){ return A.ang<B.ang; } }L[maxn*2],q[maxn*2]; inline db cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x; } inline bool OnLeft(line A,point p){ return cross(A.v,p-A.p)>-eps; } inline point GetPoint(line A,line B){ Vector v=A.p-B.p; db tmp=cross(B.v,v)/cross(A.v,B.v); return A.p+A.v*tmp; } int n,tot; inline void init(){ n=rd(); for(int i=1; i<=n; i++){ db x=rd(),y=rd(),yy=rd(); y-=eps; yy+=eps; point p1=point(0,y/x),p2=point(1,(y-x*x)/x); L[++tot]=line(p1,p2-p1,i); p1=point(0,yy/x),p2=point(1,(yy-x*x)/x); L[++tot]=line(p2,p1-p2,i); } L[++tot]=line(point(-eps,0),point(0,1),0); L[++tot]=line(point(0,inf),point(-1,0),0); L[++tot]=line(point(-inf,0),point(0,-1),0); L[++tot]=line(point(0,eps),point(1,0),0); sort(L+1,L+tot+1); } inline bool hpi(int mid){ int now=1; int head=1,tail=0; while(L[now].id>mid)now++; q[++tail]=L[now]; for(int i=now+1; i<=tot; i++){ if(L[i].id>mid)continue; while(head<tail && !OnLeft(L[i],p[tail-1]))tail--; while(head<tail && !OnLeft(L[i],p[head]))head++; q[++tail]=L[i]; if(fabs(cross(q[tail].v,q[tail-1].v))<eps){ tail--; if(OnLeft(q[tail],L[i].p))q[tail]=L[i]; } if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]); } while(head<tail && !OnLeft(q[head],p[tail-1]))tail--; while(head<tail && !OnLeft(q[tail-1],p[head]))head++; p[tail]=GetPoint(q[tail],q[head]); return tail-head>=2; } inline void work(){ int l=2,r=n,ans=1; while(l<=r){ int mid=(l+r)/2; if(hpi(mid))l=mid+1,ans=mid; else r=mid-1; } printf("%d\n",ans); } int main(){ init(); work(); return 0; } |