Submission #3890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3890	2013-08-31T09:09:38 Z	Apple_Cplus	Lonely mdic (kriii1_L)	C++	0 / 1	0 ms	1548 KB

L

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int n;
double data[300][3];

#define EPS 1e-9
#define EQ(a,b) (abs((a) - (b)) < EPS)

const double PI = acos(-1.0);

struct Point
{
	double x, y, rad;
	bool operator < (const Point &a) const
	{
		return rad < a.rad;
	}
	void norm()
	{
		double sz = hypot(x, y);
		x /= sz, y /= sz;
	}
};

Point trans(Point a, double rad)
{
	Point ret;
	ret.x = a.x * cos(rad) - a.y * sin(rad);
	ret.y = a.x * sin(rad) + a.y * cos(rad);
	return ret;
}

bool isSame[300];

int main(void)
{
	scanf("%d", &n);
	int ans = 0;

	for(int i=0;i<n;i++)
	{
		scanf("%lf %lf %lf", data[i], data[i] + 1, data[i] + 2);
		for(int j=0;j<i;j++)
		{
			if(EQ(data[i][0], data[j][0]) && EQ(data[i][1], data[j][1]) && EQ(data[i][2], data[j][2]))
			{
				ans++;
				data[i][2] = -1;
				isSame[j] = true;
				break;
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		if(data[i][2] == -1) continue;

		bool isIn = false;
		for(int j=0;j<n;j++)
		{
			if(data[j][2] == -1) continue;

			if(i == j) continue;
			double curDist = hypot(data[i][0] - data[j][0], data[i][1] - data[j][1]);
			if(curDist + data[i][2] < data[j][2] || EQ(curDist + data[i][2], data[j][2]))
			{
				isIn = true;
				break;
			}
		}

		if(isIn || isSame[i]) { ans++; continue; }

		vector <Point> pts;

		for(int j=0;j<n;j++)
		{
			if(data[j][2] == -1) continue;

			if(i == j) continue;
			double curDist = hypot(data[i][0] - data[j][0], data[i][1] - data[j][1]);

			if(!EQ(curDist + data[j][2], data[i][2]) && curDist + data[j][2] < data[i][2]) continue;
			else if (EQ(curDist + data[j][2], data[i][2]) || EQ(data[i][2] + data[j][2], curDist))
			{
				Point p;
				p.x = data[j][0] - data[i][0];
				p.y = data[j][1] - data[i][1];

				p.norm();

				p.x = p.x * data[i][2];
				p.y = p.y * data[i][2];
				pts.push_back(p);				
			}
			else if (data[i][2] + data[j][2] > curDist)
			{
				Point p;
				p.x = data[j][0] - data[i][0];
				p.y = data[j][1] - data[i][1];

				p.norm();

				p.x = p.x * data[i][2];
				p.y = p.y * data[i][2];

				double a = data[i][2], c = hypot(data[i][0] - data[j][0], data[i][1] - data[j][1]),
						b = data[j][2];

				double rad = acos((a * a + c * c - b * b) / 2 / a / c);
				
				Point p1 = trans(p, rad), p2 = trans(p, -rad);
				pts.push_back(p1);
				pts.push_back(p2);
			}
		}

		if(pts.size() <= 1) continue;
		else
		{
			for(int j=0;j<pts.size();j++)
			{
				pts[j].rad = atan2(pts[j].y, pts[j].x);
				if(pts[j].rad < 0) pts[j].rad += 2 * PI;
			}

			sort(pts.begin(), pts.end());
		
			bool isOut = false;
			for(int j=0;j<pts.size();j++)
			{
				double curRad;
				double r1 = pts[j].rad;
				double r2;
				if(j + 1 < pts.size()) r2 = pts[j + 1].rad;
				else r2 = pts[0].rad;
				while(r2 < r1) r2 += 2 * PI;

				curRad = (r1 + r2) / 2;
				while(curRad >= 2 * PI) curRad -= 2 * PI;

				Point cur;
				cur.x = data[i][2], cur.y = 0;
				cur = trans(cur, curRad);
				cur.x += data[i][0], cur.y += data[i][1];

				int cnt = 0;
				for(int k=0;k<n;k++)
				{
					if(data[k][2] == -1) continue;

					double curDist = hypot(cur.x - data[k][0], cur.y - data[k][1]);
					if(curDist < data[k][2] || EQ(curDist, data[k][2]))
					{
						cnt++;
						if(cnt == 2) break;
					}
				}

				if(cnt == 1)
				{
					isOut = true;
					break;
				}
			}

			if(isOut == false) ans++;
		}
	}

	printf("%d\n", ans);
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1548 KB	Output is correct
2	Incorrect	0 ms	1548 KB	Output isn't correct
3	Halted	0 ms	0 KB	-