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

方針

どれが線分1,2,3にそれぞれなるのかを全通り試す。
点Cが線分AB上にあるかは、ccw(A,B,C)が0であるかどうかを見ればよい。
ccwロバストなのでなるべくこれを使う。

ソースコード

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;
	}
}