Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

贴个c++代码

Posted by a280920481 at 2019-04-25 00:28:51 on Problem 1418
```#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: