Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator