Codeforces 13 B. Letter A
問題
3本の線分があたえられる。これらが以下の条件を満たしているならYESを、そうでないならNOを出力せよ。
- 2本の線分が端点を共有する。(これを線分1,線分2とする)
- 線分1と線分2のなす角は0度より大きく、90度を超えない
- 線分3が、線分1,線分2の内部の点を結んだものである
- 線分1の両端をA,B線分3の線分1上の点をPとすると、AP,BPの小さいほうを大きいほうで割った比は1/4以上である
- 同様に、線分2上の線分3の端点がつくる比も1/4以上である
制約条件
座標の絶対値≦10^8
ソースコード
EPSが1e-7,1e-8だとWAで、1e-9だと通った。
int ccw(P a, P b, P c) { b -= a; c -= a; if (cross(b, c) > 0) return +1; // counter clockwise if (cross(b, c) < 0) return -1; // clockwise if (dot(b, c) < 0) return +2; // c--a--b on line if (norm(b) < norm(c)) return -2; // a--b--c on line return 0; } P p[3][2]; bool good(int l,int pt,int k){ if(ccw(p[l][0],p[l][1],p[pt][k])!=0)return 0; double r=abs(p[pt][k]-p[l][0])/abs(p[l][1]-p[l][0]); return 0.2-EPS<r&&r<0.8+EPS; } bool solve(){ rep(a,3)rep(b,3)if(a!=b)rep(ad,2)rep(bd,2)if(p[a][ad]==p[b][bd]){ if(dot(p[a][1-ad]-p[a][ad],p[b][1-bd]-p[b][bd])<-EPS|| abs(cross(p[a][1-ad]-p[a][ad],p[b][1-bd]-p[b][bd]))<EPS)continue; rep(k,2)if(good(a,3-a-b,k)&&good(b,3-a-b,1-k))return 1; } return 0; } void run() { int t; cin>>t; while(t--){ rep(i,3)rep(j,2){ int x,y; cin>>x>>y; p[i][j]=P(x,y); } cout<<(solve()?"YES":"NO")<<endl; } }