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

() { @Override public int compare(P p1, P p2) { return p1.x>p2.x?-1:p1.xp2.y?-1:p1.y= 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

q = new ArrayList

(); 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<