Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个c++代码#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; const double pi = acos(-1.0); const double EPS = 1e-14; const int MAX_N = 100; struct P { double x; double y; P() { } P(const double & x, const double & y) :x(x), y(y) { } }; struct P2 { double x1; double y1; double x2; double y2; }; struct Circle { double x; double y; double r; }; Circle cir[MAX_N]; vector<double> kp[MAX_N]; P checkp[8 * MAX_N * MAX_N]; double dist2(const double & x1, const double & y1, const double & x2, const double & y2); double sq(const double & x); P2 circ(const Circle & c1, const Circle & c2); bool inter(const Circle & c1, const Circle & c2); bool in_cir(const Circle & c, const P & p); bool visible[MAX_N]; int main() { int N; while(true) { scanf("%d", &N); if(!N) { break; } memset(visible, false, sizeof(visible)); for(int i = 0; i < N; ++i) { scanf("%lf%lf%lf", &cir[i].x, &cir[i].y, &cir[i].r); kp[i].clear(); } for(int i = 1; i < N; ++i) { const Circle & ci = cir[i]; for(int j = 0; j < i; ++j) { const Circle & cj = cir[j]; if(inter(ci, cj)) { P2 m = circ(ci, cj); kp[i].push_back(atan2(m.y1 - ci.y, m.x1 - ci.x)); kp[i].push_back(atan2(m.y2 - ci.y, m.x2 - ci.x)); kp[j].push_back(atan2(m.y1 - cj.y, m.x1 - cj.x)); kp[j].push_back(atan2(m.y2 - cj.y, m.x2 - cj.x)); } } kp[i].push_back(-pi); kp[i].push_back(pi); } int checknum = 0; for(int i = 0; i < N; ++i) { sort(kp[i].begin(), kp[i].end()); if(!kp[i].empty()) { const Circle & c = cir[i]; const size_t & ed = kp[i].size() - 1; const double & arc = (kp[i][0] + kp[i][ed]) / 2.0; const double & _sin = sin(arc); const double & _cos = cos(arc); checkp[checknum++] = P(c.x + _cos * (c.r + EPS), c.y + _sin * (c.r + EPS)); checkp[checknum++] = P(c.x + _cos * (c.r - EPS), c.y + _sin * (c.r - EPS)); for(size_t j = 0; j < ed; ++j) { const double & arc = (kp[i][j] + kp[i][j + 1]) / 2.0; const double & _sin = sin(arc); const double & _cos = cos(arc); checkp[checknum++] = P(c.x + _cos * (c.r + EPS), c.y + _sin * (c.r + EPS)); checkp[checknum++] = P(c.x + _cos * (c.r - EPS), c.y + _sin * (c.r - EPS)); } } } int ans = 0; for(int i = 0; i < checknum; ++i) { for(int j = N - 1; j >= 0; --j) { if(in_cir(cir[j], checkp[i])) { if(!visible[j]) { ++ans; visible[j] = true; } break; } } } printf("%d\n", ans); } return 0; } double dist2(const double & x1, const double & y1, const double & x2, const double & y2) { double dx = (x2 - x1); double dy = (y2 - y1); return dx * dx + dy * dy; } double sq(const double & x) { return x * x; } P2 circ(const Circle & c1, const Circle & c2) { P2 res; P mid; double A1, B1, C1; double A2, B2, C2; A1 = (c1.y - c2.y); B1 = (c2.x - c1.x); C1 = c1.x * c2.y - c2.x * c1.y; A2 = 2.0 * B1; B2 = -2.0 * A1; C2 = (c2.r - c1.r) * (c2.r + c1.r) - B1 * (c1.x + c2.x) + A1 * (c1.y + c2.y); mid.x = (B1 * C2 - B2 * C1) / (A1 * B2 - A2 * B1); mid.y = (A1 * C2 - A2 * C1) / (A2 * B1 - A1 * B2); const double & ml = A2 * c1.x + B2 * c1.y + C2; const double & d2 = ml * ml / (A2 * A2 + B2 * B2); const double & d = sqrt(d2); const double & lil = sqrt(c1.r * c1.r - d2); const double & adx = mid.x - c1.x; const double & ady = mid.y - c1.y; const double & dx = lil * ady / d; const double & dy = -lil * adx / d; res.x1 = mid.x + dx; res.y1 = mid.y + dy; res.x2 = mid.x - dx; res.y2 = mid.y - dy; return res; } bool inter(const Circle & c1, const Circle & c2) { const double & d = sqrt(dist2(c1.x, c1.y, c2.x, c2.y)); return c1.r + c2.r >= d && c1.r + d >= c2.r && c2.r + d >= c1.r; } bool in_cir(const Circle & c, const P & p) { return dist2(c.x, c.y, p.x, p.y) <= c.r * c.r; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator