【HNOI 2012】 射箭

把方程写出来就发现每一个限制条件都是相当于坐标轴上一条直线，然后半平面交，但是我nlog^2的程序会T而且T的那几个点如果把时限开大里面还会WA,大概被卡精度。我的代码只有70...这题比较好的方法是每次插入并判断吧类似WUY每次半平面交的方法.但是我懒得改了...

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
const double eps=0.001,pi=3.1415926535897932384626433832795028841971693993751058209749446;
/////////////////////read4.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
/////////////////variables&functions////////////////////
const int maxn=222222;
struct Target
{
    double x,y1,y2;
}target;
int n,cnt;
struct Point
{
    double x,y;
    Point(double a=0,double b=0):x(a),y(b){}
    Point operator-(Point b)const{return Point(x-b.x,y-b.y);}
    double operator*(Point b)const{return x*b.y-y*b.x;}
};
#define angel angle
double mul(Point x,Point y,Point z){return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);}
struct Line
{
    Point x,y;
    double angle;
    Line(Point a=Point(0,0),Point b=Point(0,0),double c=0):x(a),y(b),angle(c){}
    bool operator<(Line b)const{return (angle==b.angel)?mul(x,b.x,b.y)>0:angle<b.angle;}
    bool operator==(Line b)const{return angle==b.angle;}
}linee[maxn],line[maxn];
inline Point intersect(Line a,Line b)
{
    double k1=(b.y-a.x)*(a.y-a.x);
    double k2=(a.y-a.x)*(b.x-a.x);
    double k=k1/(k1+k2);
    return Point(b.y.x+(b.x.x-b.y.x)*k,b.y.y+(b.x.y-b.y.y)*k);
}
bool judgee(Line x,Line y,Line z)
{
    Point temp=intersect(x,y);
    return mul(temp,z.x,z.y)<0;
}
int deq[maxn],L,R,tot;
void hpi(Line *a,int n)
{
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    L=0,R=1;
    deq[0]=1;deq[1]=2;
    rep(i,3,n)
    {
        while (L<R&&judgee(a[deq[R-1]],a[deq[R]],a[i])) R--;
        while (L<R&&judgee(a[deq[L+1]],a[deq[L]],a[i])) L++;
        deq[++R]=i;
    }
    while (L<R&&judgee(a[deq[R-1]],a[deq[R]],a[deq[L]])) R--;
    while (L<R&&judgee(a[deq[L+1]],a[deq[L]],a[deq[R]])) L++;
    deq[++R]=deq[L];
}
bool judge(int n)
{
    rep(i,1,n*2) line[i]=linee[i];
    hpi(line,n*2);
    if (R-L>2) return true;
    return false;
}
double calc(double x,double y,double z)
{
    return z/y-x*y;
}
int main()
{
    //freopen("./2053/archery9.in","r",stdin);
    read(n);
    rep(i,1,n) 
    {
        read(target.x,target.y1,target.y2);
        linee[++cnt].y=Point(10,calc(10,target.x,target.y1));
        linee[cnt].x=Point(-10,calc(-10,target.x,target.y1));
        linee[cnt].angel=atan2(linee[cnt].x.x-linee[cnt].y.x,linee[cnt].x.y-linee[cnt].y.y);

    linee[++cnt].x=Point(10,calc(10,target.x,target.y2));
    linee[cnt].y=Point(-10,calc(-10,target.x,target.y2));
    linee[cnt].angel=atan2(linee[cnt].x.x-linee[cnt].y.x,linee[cnt].x.y-linee[cnt].y.y);
    // double temp1=target.y1/target.x;
    // if (abs(temp1)&lt;eps) linee[++cnt]=Line(Point(1,temp1-target.x),Point(temp1/target.x,0),atan2(1-temp1/target.x,temp1-target.x));
    // else linee[++cnt]=Line(Point(0,temp1),Point(temp1/target.x,0),atan2(-temp1/target.x,temp1));
    // temp1=target.y2/target.x;
    // if (abs(temp1)&lt;eps) linee[++cnt]=Line(Point(temp1-target.x,1),Point(0,temp1/target.x),atan2(temp1-target.x,1-temp1/target.x));
    // else linee[++cnt]=Line(Point(temp1/target.x,0),Point(0,temp1),atan2(temp1/target.x,-temp1));
}
int L=0,R=n;
while (L&lt;R)
{
    int mid=(L+R)&gt;&gt;1;
    if (judge(mid)) L=mid+1;
    else R=mid;
    //debugdo(printf(&quot;%d %d\n&quot;,L,R));
}
printf(&quot;%d\n&quot;,L-1);
return 0;
}