• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/geo/area.cpp from [959cda21c7e42a70] to [a5ea821173c9c755].

     3      3   //   O(N)
     4      4   //
     5      5   // Verified by
     6      6   //   - SRM 337 Div1 LV3
     7      7   //   - SRM 486 Div1 LV3
     8      8   //-------------------------------------------------------------
     9      9   
    10         -double outer_prod( pt a, pt b )
    11         -{
    12         - return (a.real()*b.imag() - b.real()*a.imag())/2;
    13         -}
           10  +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
    14     11   
    15     12   double area( const vector<pt>& q )
    16     13   {
    17     14    double a = 0.0;
    18     15   
    19     16    pt o = q[0];
    20     17    for(int i=1; i+1<q.size(); ++i)
    21     18     a += outer_prod(q[i]-o, q[i+1]-o);
    22     19    return abs(a) / 2;
    23     20   }

Modified lib/geo/circle.cpp from [0f1f35288c2dfafe] to [f037935b3feedc1e].

     1         -typedef long double LD;
     2         -typedef complex<LD> CMP;
            1  +// Verified: partly by geocon2013 D(1).
     3      2   
     4         -bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
            3  +// Crosspoing of a line (not lineseg!) and a circle).
            4  +bool line_circle(CMP la, CMP lb, CMP c, double r, CMP* p1, CMP* p2)
     5      5   {
     6      6    CMP v = (lb-la) / abs(lb-la);
     7      7    CMP o = (c-la) / v;
     8      8    if( abs(o.imag()) > r )
     9      9     return false;
    10         - LD dx = sqrt(r*r - o.imag()*o.imag());
           10  + double dx = sqrt(r*r - o.imag()*o.imag());
    11     11    *p1 = la + (o.real()-dx)*v;
    12     12    *p2 = la + (o.real()+dx)*v;
    13     13    return true;
    14     14   }
           15  +
           16  +// Whether or not |p| is in the circle (c, r).
           17  +bool pt_in_circle(CMP p, CMP c, double r)
           18  +{
           19  + return norm(p-c) <= r*r;
           20  +}
           21  +
           22  +// Assuming |o| is outside (C,r), compute the two tangent points.
           23  +void sessen(CMP o, CMP c, double r, CMP* p1, CMP* p2)
           24  +{
           25  + double len = sqrt(norm(c-o) - r*r);
           26  + double theta = asin(r/abs(c-o));
           27  +
           28  + if(p1) *p1 = o+(c-o)*polar(len/abs(c-o), theta);
           29  + if(p2) *p2 = o+(c-o)*polar(len/abs(c-o), -theta);
           30  +}
           31  +
           32  +// For two points |p| and |q| on (c,r), compute their distance along the circle.
           33  +double d_on_c(CMP c, double r, CMP p, CMP q)
           34  +{
           35  + return abs(arg((p-c) / (q-c))) * r;
           36  +}

Deleted lib/geo/line_circle.cpp version [0f1f35288c2dfafe]

     1         -typedef long double LD;
     2         -typedef complex<LD> CMP;
     3         -
     4         -bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
     5         -{
     6         - CMP v = (lb-la) / abs(lb-la);
     7         - CMP o = (c-la) / v;
     8         - if( abs(o.imag()) > r )
     9         -  return false;
    10         - LD dx = sqrt(r*r - o.imag()*o.imag());
    11         - *p1 = la + (o.real()-dx)*v;
    12         - *p2 = la + (o.real()+dx)*v;
    13         - return true;
    14         -}

Modified lib/geo/pt_in_poly.cpp from [05f672d15009c4b5] to [f28d7402b7cb4529].

     2      2   //-------------------------------------------------------------
     3      3   // The circle passing three points
     4      4   //
     5      5   // Verified by
     6      6   //   - AOJ 0012 (only triangles)
     7      7   //-------------------------------------------------------------
     8      8   
     9         -double outer_prod( CMP a, CMP b )
    10         -{
    11         - return (a.real()*b.imag() - b.real()*a.imag())/2;
    12         -}
            9  +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
    13     10   
    14     11   bool point_in_polygon( vector<CMP>& ps, CMP p )
    15     12   {
    16     13    bool in = false;
    17     14    for(int i=0; i<ps.size(); ++i) {
    18     15     CMP a = ps[i] - p;
    19     16     CMP b = ps[(i+1)%ps.size()] - p;