| ||||||||||
| 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