Advertisement
yicongli

LG3222

Mar 1st, 2019
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7.  
  8. template<typename T>
  9. inline void read(T&x){
  10.     x=0;T k=1;char gc;
  11.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  12.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  13. }
  14.  
  15. #define db long double
  16.  
  17. const db eps=1e-19;
  18. const db INF=1e10;
  19. const int N=2e5+7;
  20.  
  21. inline int dcmp(const db &x){
  22.     if(fabs(x)<eps)return 0;
  23.     return x>0?1:-1;
  24. }
  25.  
  26. struct Point{
  27.     db x,y;
  28.    
  29.     inline Point(){}
  30.     inline Point(const db &_x,const db &_y):x(_x),y(_y){}
  31.    
  32. };
  33.  
  34. #define Vec Point
  35.  
  36. inline Vec operator +(const Vec &a,const Vec &b){
  37.     return Vec(a.x+b.x,a.y+b.y);
  38. }
  39.  
  40. inline Vec operator -(const Vec &a,const Vec &b){
  41.     return Vec(a.x-b.x,a.y-b.y);
  42. }
  43.  
  44. inline void operator +=(Vec &a,const Vec &b){
  45.     a.x+=b.x,a.y+=b.y;
  46. }
  47.  
  48. inline void operator -=(Vec &a,const Vec &b){
  49.     a.x-=b.x,a.y-=b.y;
  50. }
  51.  
  52. inline Vec operator *(const Vec &a,const db &b){
  53.     return Vec(a.x*b,a.y*b);
  54. }
  55.  
  56. inline Vec operator /(const Vec &a,const db &b){
  57.     return Vec(a.x/b,a.y/b);
  58. }
  59.  
  60. inline db Cross(const Vec &a,const Vec &b){
  61.     return a.x*b.y-a.y*b.x;
  62. }
  63.  
  64. inline db Angle(const Vec &a){
  65.     return atan2(a.y,a.x);
  66. }
  67.  
  68. struct Line{
  69.     Point S,T;
  70.     db theta;
  71.    
  72.     inline Line(){}
  73.     inline Line(const Point &A,const Point &B):S(A),T(B),theta(Angle(B-A)){}
  74.    
  75. };
  76.  
  77. #define Seg Line
  78.  
  79. inline bool operator < (const Line &A,const Line &B){
  80.     double alpha=A.theta-B.theta;
  81.     if(dcmp(alpha))return dcmp(alpha)==-1;
  82.     return dcmp(Cross(A.T-A.S,B.S-A.S))==-1;
  83. }
  84.  
  85. inline Point LineCross(const Line &a,const Line &b){
  86.     Vec u=a.T-a.S;
  87.     Vec v=b.T-b.S;
  88.     Vec w=a.S-b.S;
  89.     db t=Cross(v,w)/Cross(u,v);
  90.     return a.S+u*t;
  91. }
  92. //on the right or not
  93. inline bool Direction(const Line &a,const Point &A){
  94.     return dcmp(Cross(a.T-a.S,A-a.S))==-1;
  95. }
  96.  
  97. int Q[N];
  98.  
  99. inline bool Half(Line *A,int n){
  100.     sort(A+1,A+n+1);
  101.     Q[0]=1;
  102.     int head=0,tail=0;
  103.     for(int i=2;i<=n;++i){
  104.         if(!dcmp(A[i].theta-A[i-1].theta))continue;
  105.         while(head<tail&&Direction(A[i],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
  106.         while(head<tail&&Direction(A[i],LineCross(A[Q[head]],A[Q[head+1]])))++head;
  107.         Q[++tail]=i;
  108.     }
  109.     while(head<tail&&Direction(A[Q[head]],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
  110.     while(head<tail&&Direction(A[Q[tail]],LineCross(A[Q[head]],A[Q[head+1]])))++head;
  111.     return head+1<tail;
  112. }
  113.  
  114. Line A[N],B[N];
  115.  
  116. inline bool check(int x){
  117.     x*=2;
  118.     for(int i=1;i<=x;++i){
  119.         B[i]=A[i];
  120.     }
  121.     Point a(-eps,eps);
  122.     Point b(-eps,INF);
  123.     Point c(-INF,INF);
  124.     Point d(-INF,eps);
  125.     B[++x]=Line(a,b);
  126.     B[++x]=Line(b,c);
  127.     B[++x]=Line(c,d);
  128.     B[++x]=Line(d,a);
  129.     return Half(B,x);
  130. }
  131.  
  132. int main(){
  133. //  freopen(".in","r",stdin);
  134. //  freopen(".out","w",stdout);
  135.     int n,tot=0;r(n);
  136.     for(int i=1;i<=n;++i){
  137.         int x,l,r;
  138.         r(x),r(l),r(r);
  139.         A[++tot]=Line(Point(0,(db)l/x-eps),Point(1,(db)l/x-x-eps));
  140.         A[++tot]=Line(Point(1,(db)r/x-x+eps),Point(0,(db)r/x+eps));
  141.     }
  142.     int l=1,r=n,mid,ans;
  143.     while(l<=r){
  144.         mid=(l+r)>>1;
  145.         if(check(mid))ans=mid,l=mid+1;
  146.         else r=mid-1;
  147.     }
  148.     printf("%d\n",ans);
  149.     return 0;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement