#include #include #include #include using namespace std; // FLT_EPSILON だと精度が足りなかった. #define EPS 0.00000001 #define deq(a, b) ( fabs((a) - (b)) < EPS ) #define PARALLEL 0 #define ANTI_CLOCK 1 #define CLOCK (-1) #define FEASIBLE 1 #define ONLINE 0 #define INFEASIBLE (-1) class Point { public: double x, y; Point() {} Point( double x, double y ) : x(x), y(y) {} int direction( const Point &p, const Point &q ) const { const double px = p.x - x, py = p.y - y; const double qx = q.x - x, qy = q.y - y; const double op = px*qy - qx*py; if ( deq(op, 0.0) ) return PARALLEL; return (op > 0.0)? ANTI_CLOCK : CLOCK; } }; Point intersection( const Point &tb, const Point &te, const Point &sb, const Point &se ) { const double num = (tb.y - sb.y) * (se.x - sb.x) - (tb.x - sb.x) * (se.y - sb.y); const double denom = (te.x - tb.x) * (se.y - sb.y) - (te.y - tb.y) * (se.x - sb.x); assert( !deq(denom, 0.0) ); const double r = num / denom; return Point(tb.x + r*(te.x - tb.x), tb.y + r*(te.y - tb.y)); } class VertexList { public: int n, p; int feasibility; Point vertex; }; #define NPERSON_MAX 100 int nperson; double R[NPERSON_MAX], S[NPERSON_MAX], B[NPERSON_MAX]; int nused, listHead; VertexList VL[2*NPERSON_MAX]; void initList() { nused = 0; } int allocList() { return nused++; } bool cutConvex( const Point &b, const Point &e, const int direction ) { // cutConvex に入るときは必ず三角形以上の領域を切断するとする. // 切断したことにより線分や点になってしまう場合, 条件に合う領域がない場合, // つまり領域がつぶれた場合は false. それ以外は true. bool hasClock = false, hasAnticlock = false; int nparallel = 0; for ( int cs = listHead, i = 0; cs != listHead || i == 0; cs = VL[cs].n, i++ ) { const int d = b.direction(e, VL[cs].vertex); if ( d == PARALLEL ) nparallel++, VL[cs].feasibility = ONLINE; else if ( d == ANTI_CLOCK ) hasAnticlock = true, VL[cs].feasibility = (direction == ANTI_CLOCK)? FEASIBLE : INFEASIBLE; else hasClock = true, VL[cs].feasibility = (direction == CLOCK)? FEASIBLE : INFEASIBLE; } // 全て反対方向または線上. if ( direction == CLOCK && !hasClock ) return false; if ( direction == ANTI_CLOCK && !hasAnticlock ) return false; // 制約が強くない. if ( direction == ANTI_CLOCK && !hasClock ) return true; if ( direction == CLOCK && !hasAnticlock ) return true; int npushed = 0, V[2]; for ( int cs = listHead, i = 0; cs != listHead || i == 0; cs = VL[cs].n, i++ ) { if ( npushed == 2 ) continue; if ( VL[cs].feasibility == ONLINE ) { V[npushed++] = cs; continue; } if ( VL[cs].feasibility != VL[VL[cs].n].feasibility && VL[VL[cs].n].feasibility != ONLINE ) { const int n = allocList(); V[npushed++] = n; VL[n].vertex = intersection(b, e, VL[cs].vertex, VL[VL[cs].n].vertex); VL[n].p = cs; VL[n].n = VL[cs].n; VL[VL[cs].n].p = n; VL[cs].n = n; cs = n; } } assert( npushed == 2 ); listHead = V[0]; if ( VL[VL[V[0]].p].feasibility == INFEASIBLE ) VL[V[0]].p = V[1]; else VL[V[0]].n = V[1]; if ( VL[VL[V[1]].p].feasibility == INFEASIBLE ) VL[V[1]].p = V[0]; else VL[V[1]].n = V[0]; return true; } bool addConstraint( int n, int i ) { // 明らかに n より弱い相手は制約にならない. if ( R[i] <= R[n] && S[i] <= S[n] && B[i] <= B[n] ) return true; // [(1/ri - 1/rn) - (1/bi - 1/bn)] x + [(1/si - 1/sn) - (1/bi - 1/bn)] y + (1/bi - 1/bn) > 0 // ax + by + c > 0 とする. const double a = (1.0/R[i] - 1.0/R[n]) - (1.0/B[i] - 1.0/B[n]); const double b = (1.0/S[i] - 1.0/S[n]) - (1.0/B[i] - 1.0/B[n]); const double c = (1.0/B[i] - 1.0/B[n]); // constraint line. Point cb, ce; int direction; // 明らかに強い相手, 明らかに弱い相手を除くと a = b = 0 ということは起こり得ない. // a = 0 のとき sign(rn - ri) = sign(bn - bi) であり b = 0 のとき sign(sn = si) = sign(bn - bi) // である. つまり a = b = 0 のとき sign(rn - ri) = sign(sn = si) = sign(bn - bi) である. // これは n が明らかに i より強いか弱いかのどちらかであることを表している. // よって以降は a != 0 または b != 0 であると仮定できる. if ( !deq(b, 0) && b > 0 ) cb = Point(0.0, -c/b), ce = Point(1.0, -c/b - a/b), direction = ANTI_CLOCK; else if ( !deq(b, 0) ) cb = Point(0.0, -c/b), ce = Point(1.0, -c/b - a/b), direction = CLOCK; else if ( a > 0 ) cb = Point(-c/a, 0.0), ce = Point(-c/a, 1.0), direction = CLOCK; else cb = Point(-c/a, 0.0), ce = Point(-c/a, 1.0), direction = ANTI_CLOCK; return cutConvex(cb, ce, direction); } bool computeFeasibility( int nth ) { // 明らかに勝てない相手が居る場合を除く. for ( int i = 0; i < nperson; i++ ) if ( i != nth && R[i] >= R[nth] && S[i] >= S[nth] && B[i] >= B[nth] ) return false; // 2 変数による線形計画法. running の比率 x, swimming の比率 y とする. のこりが bicycle. // x > 0 // y > 0 // x + y < 1.0 // For all i != n, [(1/ri - 1/rn) - (1/bi - 1/bn)] x + [(1/si - 1/sn) - (1/bi - 1/bn)] y + (1/bi - 1/bn) > 0 initList(); // x > 0, y > 0, x + y < 1.0 による三角形初期化. const int o = allocList(), x = allocList(), y = allocList(); VL[o].n = x, VL[o].p = y, VL[o].vertex = Point(0.0, 0.0); VL[x].n = y, VL[x].p = o, VL[x].vertex = Point(1.0, 0.0); VL[y].n = o, VL[y].p = x, VL[y].vertex = Point(0.0, 1.0); listHead = o; // [(1/ri - 1/rn) - (1/bi - 1/bn)] x + [(1/si - 1/sn) - (1/bi - 1/bn)] y + (1/bi - 1/bn) > 0 for ( int i = 0; i < nperson; i++ ) if ( i != nth && !addConstraint(nth, i) ) return false; return true; } int main() { while ( cin >> nperson ) { for ( int i = 0; i < nperson; i++ ) cin >> R[i] >> S[i] >> B[i]; for ( int nth = 0; nth < nperson; nth++ ) if ( computeFeasibility(nth) ) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }