#24747 (Java) No.199 星を描こう

提出ソース
結果

問題	No.199 星を描こう
コンテスト
ユーザー	aaa
提出日時	2015-05-05 13:40:35
言語	Java (openjdk 23)
結果	AC
実行時間	156 ms / 2,000 ms
コード長	9,948 bytes
コンパイル時間	3,681 ms
コンパイル使用メモリ	92,064 KB
実行使用メモリ	41,556 KB
最終ジャッジ日時	2024-12-30 03:36:07
合計ジャッジ時間	8,532 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 25
権限があれば一括ダウンロードができます
ソースコード

raw source code
package y199;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
	static final double EPS = 1.0e-8;
	final P origin = new P(0, 0);
	final double rad = 180/Math.PI;

	/*
	 *基本
	 *
	 */

	//ベクトルのなす角度p0→p1, p1→p2のなす角。劣角限定 @ac
	static double angle(P p0, P p1, P p2) {
		P v = p1.sub(p0);
		P u = p2.sub(p1);
		return Math.acos((-v.x*u.x -v.y*u.y)/ (v.norm()*u.norm()));
	}

	//ベクトルpをlに射影 @ac
	static P proj(L l, P p) {
		double t = inp(p.sub(l.s), l.s.sub(l.t)) / l.s.sub(l.t).norm2();
		P tp = l.s.sub(l.t);
		return new P(l.s.x + t*tp.x, l.s.y + t*tp.y);
	}

	static P refl(L l, P p) {
		P tp = proj(l, p).sub(p);
		return new P(p.x + 2*tp.x, p.y + 2*tp.y);
	}
	//内積
	static double inp(P p1, P p2) {
		return p1.x*p2.x + p1.y*p2.y;
	}
	//外積
	static double extp(P p1, P p2) {
		return p1.x*p2.y - p2.x*p1.y;
	}

	//点の進行方向
	// 1 : ccw, -1: cw, 2: c--a--b, -2: a--b--c, 0:a--c--b(or a--c=b)
	//a b c が反時計　1
	//a b c が時計 -1
	//直線a b上にcが乗ってると0
	static int ccw(P a, P b, P c) {
		P p = b.sub(a), q = c.sub(a);
		if (extp(p, q) > EPS)    return +1;
		if (extp(p, q) < -EPS)    return -1;
		if (inp(p, q) < -EPS)     return +2;
		if (p.norm() + EPS < q.norm()) return -2;
		return 0;
	}
	/*
	 * 交差判定など
	 *
	 */

	//直線の交差判定と
	static boolean intersectLL(L l, L m) {
		return Math.abs(extp(l.t.sub(l.s), m.t.sub(m.s))) > EPS || // non-parallel
				Math.abs(extp(l.t.sub(l.s), m.s.sub(l.s))) < EPS;   // same line
	}
	static boolean intersectLS(L l, L s) {
		return extp(l.t.sub(l.s), s.s.sub(l.s))*       // s.s is left of l
				extp(l.t.sub(l.s), s.t.sub(l.t)) < EPS; // s.t is right of l
	}
	static boolean intersectSS(L s, L t) {
		return ccw(s.s,s.t,t.s)*ccw(s.s,s.t,t.t) <= 0 &&
				ccw(t.s,t.t,s.s)*ccw(t.s,t.t,s.t) <= 0;
	}
	static boolean intersectSP(L s, P p) {
		return ccw(s.s, s.t, p) == 0;
		//return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
	}

	/*
	 * 距離など
	 */
	static double distanceLP(L l, P p) {
		return p.sub(proj(l, p)).norm();
	}
	static double distanceLL(L l, L m) {
		return intersectLL(l, m) ? 0 : distanceLP(l, m.s);
	}
	static double distanceLS(L l, L s) {
		if (intersectLS(l, s)) return 0;
		return Math.min(distanceLP(l, s.s), distanceLP(l, s.t));
	}
	static double distanceSP(L s, P p) {
		P r = proj(s, p);
		if (intersectSP(s, r)) return r.sub(p).norm();
		return Math.min(s.s.sub(p).norm(), s.t.sub(p).norm());
	}
	static double distanceSS(L s, L t) {
		if (intersectSS(s, t)) return 0;
		return Math.min(Math.min(distanceSP(s, t.s), distanceSP(s, t.t)),
				Math.min(distanceSP(t, s.s), distanceSP(t, t.t)));
	}

	/*
	 * 交点
	 *
	 */

	//直線の交点@ac

	//直線と直線の交点
	P isLL(P p1, P p2, P q1, P q2) {
		double d = q2.sub(q1).det(p2.sub(p1));
		if (Math.abs(d) < EPS) return null;
		return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1)) / d));
	}

	//Precondition: 平行でない
	static P crosspoint(L l, L m) {
		double A = extp(l.t.sub(l.s), m.t.sub(m.s));
		double B = extp(l.t.sub(l.s), l.t.sub(m.s));
		if (Math.abs(A) < EPS && Math.abs(B) < EPS) return m.s; // same line
		if (Math.abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
		P tp = m.t.sub(m.s);
		return new P(m.s.x + B/A*tp.x, m.s.y + B/A*tp.y);
	}

	//平行判定？
	static boolean isParallel(L l, L m) {
		double A = extp(l.t.sub(l.s), m.t.sub(m.s));
		return (Math.abs(A) < EPS);
	}
	//直交判定？
	static boolean isOrthogonal(L l, L m) {
		double A = inp(l.t.sub(l.s), m.t.sub(m.s));
		return (Math.abs(A) < EPS);
	}

	static P crosspoint(P s1, P t1, P s2, P t2) {
		double A = extp(t1.sub(s1), t2.sub(s2));
		double B = extp(t1.sub(s1), t1.sub(s2));
		if (Math.abs(A) < EPS && Math.abs(B) < EPS) return s2; // same line
		if (Math.abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
		P tp = t2.sub(s2);
		return new P(s2.x + B/A*tp.x, s2.y + B/A*tp.y);
	}

	/*
	 *
	 * 面積系
	 */

	//多角形の面積
	static double area(P[] p) {
		double s = 0;
		for(int i=0; i<p.length; i++) {
			int j = (i+1)%p.length;
			s += extp(p[i], p[j]);
		}
		s /= 2; //誤差を避けたいときには割らない
		return Math.abs(s);
	}

	//円c1, c2の共通部分の面積
	static double cc_area(Circle c1, Circle c2) {
		double d = c1.p.sub(c2.p).norm();
		if(c1.r + c2.r <= d+EPS) {
			return 0;
		}
		else if(d <= Math.abs(c1.r - c2.r) + EPS) {
			double r = Math.min(c1.r, c2.r);
			return r*r*Math.PI;
		}
		else {
			double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
			double theta = Math.acos(rc / c1.r);
			double phi = Math.acos((d - rc) / c2.r);
			return c1.r*c1.r*theta + c2.r*c2.r*phi - d*c1.r*Math.sin(theta);
		}
	}

	/*
	 * 凸多角形
	 */

	//凸性判定
	//Precondition: 3点以上
	static boolean isConvex(P[] p) {
		for (int i = 0; i < p.length; ++i) {
			int next = (i+1)%p.length;
			int prev = (i-1+p.length)%p.length;
			if (ccw(p[prev], p[i], p[next]) > 0) {
				return false;
			}
		}
		return true;
	}

	//凸包を求める
	//Precondition: 3点以上
	static P[] convex_hull(P[] p) {
		int n = p.length, k = 0;
//		p = Arrays.copyOf(p, p.length);//pの順序の保守が必要な場合
		Arrays.sort(p, 0, n, new Comparator<P>() {
			@Override
			public int compare(P p1, P p2) {
				return p1.x>p2.x?-1:p1.x<p2.x?1:p1.y>p2.y?-1:p1.y<p2.y?1:0;
			}});
		P[] ch = new P[2*n];
		for (int i=0; i<n; ch[k++] = p[i++]) // lower-hull
			while (k >= 2 && ccw(ch[k-2], ch[k-1], p[i]) <= 0) --k;
		for (int i = n-2, t = k+1; i >= 0; ch[k++] = p[i--]) // upper-hull
			while (k >= t && ccw(ch[k-2], ch[k-1], p[i]) <= 0) --k;
		return Arrays.copyOf(ch, k-1);
	}

	//最遠点対距離
	//Precondition: p[]は反時計回りの凸包
	static double farthest(P[] p) {
		int is = 0, js = 0;
		for (int i = 1; i < p.length; ++i) {
			if (p[i].y > p[is].y) is = i;
			if (p[i].y < p[js].y) js = i;
		}
		double maxd = p[is].sub(p[js]).norm();
		int i=is, j=js;
		//int maxi=i, maxj=j;
		do {
			int ni = (i+1)%p.length;
			int nj = (j+1)%p.length;
			if (extp(p[ni].sub(p[i]), p[nj].sub(p[j])) >= 0)
				j = (j+1) % p.length;
			else i = (i+1) % p.length;
			if (p[i].sub(p[j]).norm() > maxd) {
				maxd = p[i].sub(p[j]).norm();
				//maxi = i; maxj=j;
			}
		} while (i != is || j != js);
		return maxd; /* farthest pair is (maxi, maxj). */
	}

	//凸包の切断、lの左側を残す
	static P[] convex_cut(P[] p, L l) {
		List<P> q = new ArrayList<P>();
		for (int i = 0; i < p.length; ++i) {
			P a= p[i], b = p[(i+1)%p.length];
			if (ccw(l.s, l.t, a) != -1) q.add(a);
			if (ccw(l.s, l.t, a)*ccw(l.s, l.t, b) < 0)
				q.add(crosspoint(new L(a, b), l));
		}
		return q.toArray(new P[q.size()]);
	}

	/*
	 * データ構造など
	 *
	 */
	static class P {
		double x,y;
		P(double _x, double _y) { x = _x; y = _y; }
		public String toString() {return "(" +x+", "+ y +")";}
		P sub(P p) { return new P(x-p.x, y-p.y); }
		P add(P p){  return new P(x+p.x, y+p.y); }
		P mul(double m){ return new P(x*m, y*m); }
		P div(double d){ return new P(x/d, y/d); }
		double abs(){ return Math.sqrt(abs2()); }
		double abs2(){ return x*x+y*y; }
		double arg(){ return Math.atan2(y, x); }
		double myarg() {
			double arg = Math.atan2(y, x);
			if(arg < 0)
				return 2.0*Math.PI + arg;
			else
				return arg;
		}
		// inner product
		double dot(P p){ return x*p.x+y*p.y; }
		// outer product
		double det(P p){ return x*p.y-y*p.x; }
		P rot90(){ return new P(-y, x); }
		// conjugation
		P conj(){ return new P(x, -y); }
		double norm() { return Math.sqrt(norm2()); }
		double norm2() { return x*x + y*y; }
	}

	//直線or線分のクラス
	static class L {
		P s,t;
		L(P _s, P _t) { s = _s; t = _t; }
		public String toString() {return s.toString() + " -> " + t.toString();}
	}

	//円のクラス中心pで半径r
	static class Circle {
		P p;
		double r;
		Circle(P _p, double _r) { p = _p; r = _r; }
		public String toString() {
			return "center=" + p.toString() + " radius=" + r;
		}
	}

	//点 p をから引いた接線の接点
	P[] tanCP(P c, double r, P p) {
		double x = p.sub(c).abs2();
		double d = x - r * r;
		if (d < -EPS) return new P[0];
		if (d < 0) d = 0;
		P q1 = p.sub(c).mul(r * r / x);
		P q2 = p.sub(c).mul(-r * Math.sqrt(d) / x).rot90();
		return new P[]{c.add(q1.sub(q2)), c.add(q1.add(q2))};
	}

	//2円の交点
	P[] isCC(P c1, double r1, P c2, double r2) {
		double x = c1.sub(c2).abs2();
		double y = ((r1 * r1 - r2 * r2) / x + 1) / 2;
		double d = r1 * r1 / x - y * y;
		if (d < -EPS) return new P[0];
		if (d < 0) d = 0;
		P q1 = c1.add(c2.sub(c1).mul(y));
		P q2 = c2.sub(c1).mul(Math.sqrt(d)).rot90();
		return new P[]{q1.sub(q2), q1.add(q2)};
	}
	
	static P cor[];
	static boolean rec(int i, int bit, int[] perm) {
		if(i == 5) {
			L line[] = new L[5];
			for(int j = 0; j < 5; j++) {
				line[j] = new L(cor[perm[j]], cor[perm[(j+1)%5]]);
			}
			for(int j = 0; j < 5; j++) {
				L a = line[j];
				L b = line[(j+2)%5];
				L c = line[(j+3)%5];
				if(!intersectSS(a, b) || !intersectSS(a, c)) {
					return false;
				}
			}
			return true;
		}
		for(int j = 0; j < 5; j++) {
			if(((1<<j)&bit) != 0)
				continue;
			perm[i] = j;
			if(rec(i+1, bit|(1<<j), perm)) {
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		cor = new P[5];
		for(int i = 0; i < 5; i++) {
			cor[i] = new P(sc.nextInt(), sc.nextInt());
		}
		for(int i = 0; i < 5; i++)
			for(int j = 0; j < 5; j++)
				for(int k = 0; k < 5; k++) {
					if(Integer.bitCount((1<<i)|(1<<j)|(1<<k)) != 3)
						continue;
					if(ccw(cor[i], cor[j], cor[k]) == 0) {
						System.out.println("NO");
						return;
					}
				}
		if(rec(0, 0, new int[5])) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}
yukicoder

結果

ソースコード
