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