zoj 3419 Detector Placement

zoj 3419 Detector Placement

#include <iostream>#include <iomanip>#include <sstream>#include <cstdio>#include <string>#include <vector>#include <algorithm>#include <complex>#include <cstring>#include <cstdlib>#include <cmath>#include <cassert>#include <climits>#include <queue>#include <set>#include <map>#include <valarray>#include <bitset>#include <stack>using namespace std;#define REP(i,n) for(int i=0;i<(int)n;++i)#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)#define ALL(c) (c).begin(), (c).end()#define chmax(a,b) (a<(b)?(a=b,1):0)#define chmin(a,b) (a>(b)?(a=b,1):0)#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)typedef long long ll;typedef pair<int,int> pii;#define double long doubleconst double INF = 1e20;const double PI = acos(-1);const double EPS = 1e-8;typedef complex<double> P;namespace std { bool operator < (const P& a, const P& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); }}double cross(const P& a, const P& b) { return imag(conj(a)*b);}double dot(const P& a, const P& b) { return real(conj(a)*b);}struct L : public vector<P> { L(const P &a, const P &b) { push_back(a); push_back(b); } L() {}};ostream &operator<<(ostream &os, const L &a) { os << a[0] << " -> " << a[1]; return os;}typedef vector<P> G;#define curr(P, i) P[i]#define next(P, i) P[(i+1)%P.size()]struct C { P p; double r; C(const P &p, double r) : p(p), r(r) { }};int ccw(P a, P b, P c) { b -= a; c -= a; if (cross(b, c) > EPS) return +1; if (cross(b, c) < -EPS) return -1;  if (dot(b, c) < 0) return +2;  if (norm(b) < norm(c)) return -2;  return 0;}bool intersectLL(const L &l, const L &m) { return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || abs(cross(l[1]-l[0], m[0]-l[0])) < EPS; }bool intersectLS(const L &l, const L &s) { return cross(l[1]-l[0], s[0]-l[0])*  cross(l[1]-l[0], s[1]-l[0]) < EPS; }bool intersectLP(const L &l, const P &p) { return abs(cross(l[1]-p, l[0]-p)) < EPS;}bool intersectSS(const L &s, const L &t) { return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 && ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;}bool intersectSS2(const L &s, const L &t) {  REP(i, 2) { if (ccw(s[0], s[1], t[i]) == 0) { int c = ccw(s[0],s[1],t[!i]); if (s[0] == t[i]) { if (c!=-2&&c) return 0; } else if (s[1] == t[i]) { if (c!=2&&c) return 0; } else if (abs(c)==1) return 0; } } return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 && ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;}bool intersectSP(const L &s, const P &p) { return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; }P projection(const L &l, const P &p) { double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]); return l[0] + t*(l[0]-l[1]);}P reflection(const L &l, const P &p) { return p + P(2,0) * (projection(l, p) - p);}double distanceLP(const L &l, const P &p) { return abs(p - projection(l, p));}double distanceLL(const L &l, const L &m) { return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);}double istanceLS(const L &l, const L &s) { if (intersectLS(l, s)) return 0; return min(distanceLP(l, s[0]), distanceLP(l, s[1]));}double distanceSP(const L &s, const P &p) { const P r = projection(s, p); if (intersectSP(s, r)) return abs(r - p); return min(abs(s[0] - p), abs(s[1] - p));}double distanceSS(const L &s, const L &t) { if (intersectSS(s, t)) return 0; return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])), min(distanceSP(t, s[0]), distanceSP(t, s[1])));}P crosspoint(const L &l, const L &m) { double A = cross(l[1] - l[0], m[1] - m[0]); double B = cross(l[1] - l[0], l[1] - m[0]); if (abs(A) < EPS && abs(B) < EPS) return m[0];  if (abs(A) < EPS) assert(false);  return m[0] + B / A * (m[1] - m[0]);}bool intersectLHL(const L &l, const L &m) { if (!intersectLL(l,m)) return 0; P cp = crosspoint(l,m); if (ccw(m[0],m[1],cp) == 2) return 0; return 1;}bool intersectHLS(const L &l, const L &s) { if (!intersectLS(l,s)) return 0; P cp = crosspoint(l,s); if (ccw(l[0],l[1],cp) == 2) return 0; return 1;}double area(const G& g) { double A = 0; for (int i = 0; i < g.size(); ++i) { A += cross(g[i], next(g, i)); } return abs(A/2);}G convex_cut(const G& g, const L& l) { G Q; REP(i, g.size()) { P A = curr(g, i), B = next(g, i); if (ccw(l[0], l[1], A) != -1) Q.push_back(A); if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0) Q.push_back(crosspoint(L(A, B), l)); } return Q;}P centroid(const vector<P> &v) { double S = 0; P res; REP(i,v.size()) { int j = i+1; if (j == v.size()) j = 0; double tmp = cross(v[i], v[j]); S += tmp; res += (v[i] + v[j]) * tmp; } S /= 2; res /= 6*S; return res;}double manDistanceSP(const L &l, const P &p) { double res = INF; L xl = L(p, p + P(1,0)); if (intersectLS(xl, l)){ P cp = crosspoint(xl, l); double d = abs(p-cp); res = min(res, d); } L yl = L(p, p + P(0,1)); if (intersectLS(yl, l)) { P cp = crosspoint(yl, l); double d = abs(p-cp); res = min(res, d); } res = min(res, abs(l[0].real()-p.real()) + abs(l[0].imag()-p.imag())); res = min(res, abs(l[1].real()-p.real()) + abs(l[1].imag()-p.imag())); return res;}bool convex_contain(const G &g, const P &p) { REP(i,g.size()) if (ccw(g[i], next(g, i), p) == -1) return 0; return 1;}bool intersectGG(const G &g1, const G &g2) { if (convex_contain(g1, g2[0])) return 1; if (convex_contain(g2, g1[0])) return 1; REP(i,g1.size()) REP(j,g2.size()) { if (intersectSS(L(g1[i], next(g1, i)), L(g2[j], next(g2, j)))) return 1; } return 0;}double distanceGP(const G &g, const P &p) { if (convex_contain(g, p)) return 0; double res = INF; REP(i, g.size()) { res = min(res, distanceSP(L(g[i], next(g, i)), p)); } return res;}L bisector(const P &a, const P &b) { P A = (a+b)*P(0.5,0); return L(A, A+(b-a)*P(0, PI/2));}double angle(const P &a, const P &b) { double ret = arg(b)-arg(a); return (ret>=0) ? ret : ret + 2*PI;}double angle2(const P &a, const P &b) {  return min(angle(a,b), angle(b,a));}double rtod(double rad) { return rad*180/PI;}double dtor(double deg) {  return deg*PI/180;}int quadrant(const P &a) {  if (a.real() > 0 && a.imag() >= 0) return 0; if (a.real() <= 0 && a.imag() > 0) return 1; if (a.real() < 0 && a.imag() <= 0) return 2; return 3;}bool cmpAngle(const P &a, const P&b) { int q1 = quadrant(a); int q2 = quadrant(b); if (q1 != q2) return q1 < q2; return cross(a,b)>0;}P rotate(P p, double ang) { return p * P(cos(ang), sin(ang));}L rotate(L l, double ang) { return L(rotate(l[0], ang),rotate(l[1], ang));}double rr;L func(L in, L surface, bool f) { P cp = crosspoint(in,surface); P vert = surface[1] - surface[0]; vert = rotate(vert, PI/2); L vline(cp, cp+vert); if (ccw(surface[0], surface[1], in[0]) == 1 && ccw(surface[0], surface[1], vline[1]) == -1 || ccw(surface[0], surface[1], in[0]) == -1 && ccw(surface[0], surface[1], vline[1]) == 1) { vert = rotate(vert, PI); vline[1] = cp+vert; } double theta = angle2(vert, in[0]-cp); double theta2 = 0; if (f) { assert(rr*sin(theta) <= 1); theta2 = asin(rr*sin(theta)); } else { assert(sin(theta)/rr <= 1); theta2 = asin(sin(theta)/rr); } P ans; P hoge = rotate(vert,PI);  if (ccw(vline[0],vline[1], in[0]) == 1) { ans = rotate(hoge, theta2); } else { ans = rotate(hoge, -theta2); } return L(cp, cp + ans);}void solve(L laser_line) { L xaxis(P(0,0), P(1,0));  if (intersectLHL(xaxis, laser_line)) { P cp = crosspoint(xaxis, laser_line); double ans = cp.real(); if (ans > -0.0005 && ans < 0) ans = 0; cout << fixed << setprecision(3) << ans << endl; } else { puts("Error"); }}int main() { int T; scanf("%d", &T); while(T--) { P laser; cin >> laser.real() >> laser.imag(); P laser2; cin >> laser2.real() >> laser2.imag(); L laser_line(laser, laser2); P tri[3]; REP(i,3) cin >> tri[i].real() >> tri[i].imag(); cin >> rr; int cross_line = -1; double min_dist = INF; REP(i,3) { L tt(tri[i], tri[(i+1)%3]); if (intersectHLS(laser_line, tt)) { double d = abs(laser - crosspoint(laser_line, tt)); if (d < min_dist) { min_dist = d; cross_line = i; } } } if (cross_line == -1) { solve(laser_line); continue; } L tt(tri[cross_line], tri[(cross_line+1)%3]); laser_line = func(laser_line, tt, 0); int c_line2 = -1; REP(i,3) { if (i == cross_line) continue;  L tt(tri[i], tri[(i+1)%3]); if (intersectHLS(laser_line, tt)) { c_line2 = i; } } assert(c_line2 != -1); L tt2(tri[c_line2], tri[(c_line2+1)%3]); laser_line = func(laser_line, tt2, 1); solve(laser_line); }}