题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2732
题意：见原题面。
肯定是要二分答案的，判定能不能穿过一个线段的时候就是两个不等式，那么就是半平面交了...
这题精度奥妙重重... 删掉 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 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 400005 #define inf 1e12 #define ll long long 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; } int n; struct point { double x,y; friend point operator +(const point &a,const point &b) {return (point){a.x+b.x,a.y+b.y};} friend point operator -(const point &a,const point &b) {return (point){a.x-b.x,a.y-b.y};} friend double operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;} friend point operator *(const point &a,const double &b) {return (point){a.x*b,a.y*b};} }p[N]; struct line { point p,v; double det; int id; void add(point a,point b) { p=a,v=b; det=atan2(v.y,v.x); } friend bool operator <(const line &a,const line &b) {return a.det==b.det?a.v*(b.p-a.p):a.det<b.det;} friend point operator ^(const line &a,const line &b) { point tmp=a.p-b.p; double rate=(b.v*tmp)/(a.v*b.v); return a.p+a.v*rate; } }a[N],l[N],stk[N]; bool judge(point a,line t) {return t.v*(a-t.p)<0;} int top,m; bool half_plane(int n) { top=0; for(int i=1;i<=n;i++) if(l[i].det!=l[i-1].det||i==1)l[++top]=l[i]; int L=1,R=0; n=top,top=0; stk[++R]=l[1],stk[++R]=l[2]; for(int i=3;i<=n;i++) { while(L<R&&judge(stk[R]^stk[R-1],l[i]))R--; while(L<R&&judge(stk[L]^stk[L+1],l[i]))L++; stk[++R]=l[i]; } while(L<R&&judge(stk[R]^stk[R-1],stk[L]))R--; while(L<R&&judge(stk[L]^stk[L+1],stk[R]))L++; top=R-L+1; return top>=3; } bool ck(int n) { int t=0; for(int i=1;i<=m;i++)if(a[i].id<=n) l[++t]=a[i]; return half_plane(t); } int main() { n=read(); a[++m].add((point){0,0},(point){inf,0}); a[++m].add((point){0,0},(point){0,inf}); a[++m].add((point){0,inf},(point){-1,0}); a[++m].add((point){-inf,0},(point){0,-1}); for(int i=1;i<=n;i++) { double x=read(),Y1=read(),Y2=read(); a[++m].add((point){0,Y1/x},(point){1,-x}); a[m].id=i; a[++m].add((point){0,Y2/x},(point){-1,x}); a[m].id=i; } sort(a+1,a+m+1); int l=1,r=n,ret=0; while(l<=r) { int mid=(l+r)>>1; if(ck(mid))ret=mid,l=mid+1; else r=mid-1; } printf("%d\n",ret); return 0; } |
Comments | NOTHING