Overview
| SHA1 Hash: | 07ad2e1283e6d259676c512dd95110620b12cef3 |
|---|---|
| Date: | 2013-06-30 08:35:05 |
| User: | kinaba |
| Comment: | Geocon library update. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/geo/area.cpp from [959cda21c7e42a70] to [a5ea821173c9c755].
3 // O(N) 3 // O(N) 4 // 4 // 5 // Verified by 5 // Verified by 6 // - SRM 337 Div1 LV3 6 // - SRM 337 Div1 LV3 7 // - SRM 486 Div1 LV3 7 // - SRM 486 Div1 LV3 8 //------------------------------------------------------------- 8 //------------------------------------------------------------- 9 9 10 double outer_prod( pt a, pt b ) | 10 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } 11 { < 12 return (a.real()*b.imag() - b.real()*a.imag())/2; < 13 } < 14 11 15 double area( const vector<pt>& q ) 12 double area( const vector<pt>& q ) 16 { 13 { 17 double a = 0.0; 14 double a = 0.0; 18 15 19 pt o = q[0]; 16 pt o = q[0]; 20 for(int i=1; i+1<q.size(); ++i) 17 for(int i=1; i+1<q.size(); ++i) 21 a += outer_prod(q[i]-o, q[i+1]-o); 18 a += outer_prod(q[i]-o, q[i+1]-o); 22 return abs(a) / 2; 19 return abs(a) / 2; 23 } 20 }
Modified lib/geo/circle.cpp from [0f1f35288c2dfafe] to [f037935b3feedc1e].
1 typedef long double LD; | 1 // Verified: partly by geocon2013 D(1). 2 typedef complex<LD> CMP; < 3 2 > 3 // Crosspoing of a line (not lineseg!) and a circle). 4 bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2) | 4 bool line_circle(CMP la, CMP lb, CMP c, double r, CMP* p1, CMP* p2) 5 { 5 { 6 CMP v = (lb-la) / abs(lb-la); 6 CMP v = (lb-la) / abs(lb-la); 7 CMP o = (c-la) / v; 7 CMP o = (c-la) / v; 8 if( abs(o.imag()) > r ) 8 if( abs(o.imag()) > r ) 9 return false; 9 return false; 10 LD dx = sqrt(r*r - o.imag()*o.imag()); | 10 double dx = sqrt(r*r - o.imag()*o.imag()); 11 *p1 = la + (o.real()-dx)*v; 11 *p1 = la + (o.real()-dx)*v; 12 *p2 = la + (o.real()+dx)*v; 12 *p2 = la + (o.real()+dx)*v; 13 return true; 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 // The circle passing three points 3 // The circle passing three points 4 // 4 // 5 // Verified by 5 // Verified by 6 // - AOJ 0012 (only triangles) 6 // - AOJ 0012 (only triangles) 7 //------------------------------------------------------------- 7 //------------------------------------------------------------- 8 8 9 double outer_prod( CMP a, CMP b ) | 9 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } 10 { < 11 return (a.real()*b.imag() - b.real()*a.imag())/2; < 12 } < 13 10 14 bool point_in_polygon( vector<CMP>& ps, CMP p ) 11 bool point_in_polygon( vector<CMP>& ps, CMP p ) 15 { 12 { 16 bool in = false; 13 bool in = false; 17 for(int i=0; i<ps.size(); ++i) { 14 for(int i=0; i<ps.size(); ++i) { 18 CMP a = ps[i] - p; 15 CMP a = ps[i] - p; 19 CMP b = ps[(i+1)%ps.size()] - p; 16 CMP b = ps[(i+1)%ps.size()] - p;