Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- #define db long double
- const db eps=1e-19;
- const db INF=1e10;
- const int N=2e5+7;
- inline int dcmp(const db &x){
- if(fabs(x)<eps)return 0;
- return x>0?1:-1;
- }
- struct Point{
- db x,y;
- inline Point(){}
- inline Point(const db &_x,const db &_y):x(_x),y(_y){}
- };
- #define Vec Point
- inline Vec operator +(const Vec &a,const Vec &b){
- return Vec(a.x+b.x,a.y+b.y);
- }
- inline Vec operator -(const Vec &a,const Vec &b){
- return Vec(a.x-b.x,a.y-b.y);
- }
- inline void operator +=(Vec &a,const Vec &b){
- a.x+=b.x,a.y+=b.y;
- }
- inline void operator -=(Vec &a,const Vec &b){
- a.x-=b.x,a.y-=b.y;
- }
- inline Vec operator *(const Vec &a,const db &b){
- return Vec(a.x*b,a.y*b);
- }
- inline Vec operator /(const Vec &a,const db &b){
- return Vec(a.x/b,a.y/b);
- }
- inline db Cross(const Vec &a,const Vec &b){
- return a.x*b.y-a.y*b.x;
- }
- inline db Angle(const Vec &a){
- return atan2(a.y,a.x);
- }
- struct Line{
- Point S,T;
- db theta;
- inline Line(){}
- inline Line(const Point &A,const Point &B):S(A),T(B),theta(Angle(B-A)){}
- };
- #define Seg Line
- inline bool operator < (const Line &A,const Line &B){
- double alpha=A.theta-B.theta;
- if(dcmp(alpha))return dcmp(alpha)==-1;
- return dcmp(Cross(A.T-A.S,B.S-A.S))==-1;
- }
- inline Point LineCross(const Line &a,const Line &b){
- Vec u=a.T-a.S;
- Vec v=b.T-b.S;
- Vec w=a.S-b.S;
- db t=Cross(v,w)/Cross(u,v);
- return a.S+u*t;
- }
- //on the right or not
- inline bool Direction(const Line &a,const Point &A){
- return dcmp(Cross(a.T-a.S,A-a.S))==-1;
- }
- int Q[N];
- inline bool Half(Line *A,int n){
- sort(A+1,A+n+1);
- Q[0]=1;
- int head=0,tail=0;
- for(int i=2;i<=n;++i){
- if(!dcmp(A[i].theta-A[i-1].theta))continue;
- while(head<tail&&Direction(A[i],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
- while(head<tail&&Direction(A[i],LineCross(A[Q[head]],A[Q[head+1]])))++head;
- Q[++tail]=i;
- }
- while(head<tail&&Direction(A[Q[head]],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
- while(head<tail&&Direction(A[Q[tail]],LineCross(A[Q[head]],A[Q[head+1]])))++head;
- return head+1<tail;
- }
- Line A[N],B[N];
- inline bool check(int x){
- x*=2;
- for(int i=1;i<=x;++i){
- B[i]=A[i];
- }
- Point a(-eps,eps);
- Point b(-eps,INF);
- Point c(-INF,INF);
- Point d(-INF,eps);
- B[++x]=Line(a,b);
- B[++x]=Line(b,c);
- B[++x]=Line(c,d);
- B[++x]=Line(d,a);
- return Half(B,x);
- }
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n,tot=0;r(n);
- for(int i=1;i<=n;++i){
- int x,l,r;
- r(x),r(l),r(r);
- A[++tot]=Line(Point(0,(db)l/x-eps),Point(1,(db)l/x-x-eps));
- A[++tot]=Line(Point(1,(db)r/x-x+eps),Point(0,(db)r/x+eps));
- }
- int l=1,r=n,mid,ans;
- while(l<=r){
- mid=(l+r)>>1;
- if(check(mid))ans=mid,l=mid+1;
- else r=mid-1;
- }
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement