Index: lib/geo/area.cpp ================================================================== --- lib/geo/area.cpp +++ lib/geo/area.cpp @@ -5,14 +5,11 @@ // Verified by // - SRM 337 Div1 LV3 // - SRM 486 Div1 LV3 //------------------------------------------------------------- -double outer_prod( pt a, pt b ) -{ - return (a.real()*b.imag() - b.real()*a.imag())/2; -} +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } double area( const vector& q ) { double a = 0.0; ADDED lib/geo/circle.cpp Index: lib/geo/circle.cpp ================================================================== --- lib/geo/circle.cpp +++ lib/geo/circle.cpp @@ -0,0 +1,36 @@ +// Verified: partly by geocon2013 D(1). + +// Crosspoing of a line (not lineseg!) and a circle). +bool line_circle(CMP la, CMP lb, CMP c, double r, CMP* p1, CMP* p2) +{ + CMP v = (lb-la) / abs(lb-la); + CMP o = (c-la) / v; + if( abs(o.imag()) > r ) + return false; + double dx = sqrt(r*r - o.imag()*o.imag()); + *p1 = la + (o.real()-dx)*v; + *p2 = la + (o.real()+dx)*v; + return true; +} + +// Whether or not |p| is in the circle (c, r). +bool pt_in_circle(CMP p, CMP c, double r) +{ + return norm(p-c) <= r*r; +} + +// Assuming |o| is outside (C,r), compute the two tangent points. +void sessen(CMP o, CMP c, double r, CMP* p1, CMP* p2) +{ + double len = sqrt(norm(c-o) - r*r); + double theta = asin(r/abs(c-o)); + + if(p1) *p1 = o+(c-o)*polar(len/abs(c-o), theta); + if(p2) *p2 = o+(c-o)*polar(len/abs(c-o), -theta); +} + +// For two points |p| and |q| on (c,r), compute their distance along the circle. +double d_on_c(CMP c, double r, CMP p, CMP q) +{ + return abs(arg((p-c) / (q-c))) * r; +} DELETED lib/geo/line_circle.cpp Index: lib/geo/line_circle.cpp ================================================================== --- lib/geo/line_circle.cpp +++ lib/geo/line_circle.cpp @@ -1,14 +0,0 @@ -typedef long double LD; -typedef complex CMP; - -bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2) -{ - CMP v = (lb-la) / abs(lb-la); - CMP o = (c-la) / v; - if( abs(o.imag()) > r ) - return false; - LD dx = sqrt(r*r - o.imag()*o.imag()); - *p1 = la + (o.real()-dx)*v; - *p2 = la + (o.real()+dx)*v; - return true; -} Index: lib/geo/pt_in_poly.cpp ================================================================== --- lib/geo/pt_in_poly.cpp +++ lib/geo/pt_in_poly.cpp @@ -4,14 +4,11 @@ // // Verified by // - AOJ 0012 (only triangles) //------------------------------------------------------------- -double outer_prod( CMP a, CMP b ) -{ - return (a.real()*b.imag() - b.real()*a.imag())/2; -} +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } bool point_in_polygon( vector& ps, CMP p ) { bool in = false; for(int i=0; i