Submission #3689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3689	2013-08-31T07:41:59 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;
}

int main(void)
{
	scanf("%d", &n);
	for(int i=0;i<n;i++) scanf("%lf %lf %lf", data[i], data[i] + 1, data[i] + 2);
	int ans = 0;
	for(int i=0;i<n;i++)
	{
		bool isIn = false;
		for(int j=0;j<n;j++)
		{
			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) { ans++; continue; }

		vector <Point> pts;

		for(int j=0;j<n;j++)
		{
			if(i == j) continue;
			if(EQ(data[i][2] + data[j][2], hypot(data[i][0] - data[j][0], data[i][1] - data[j][1])))
			{
				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] > hypot(data[i][0] - data[j][0], data[i][1] - data[j][1]))
			{
				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 / b / c);
				
				Point p1 = trans(p, rad), p2 = trans(p, -rad);
				pts.push_back(p1);
				pts.push_back(p2);
			}
		}

		if(pts.size() <= 1) { ans++; 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;
				if(j == pts.size() - 1) curRad = (pts[j].rad + pts[0].rad + 2 * PI) / 2;
				else curRad = (pts[j].rad + pts[j + 1].rad) / 2;

				if(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++)
				{
					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) ans++;
		}
	}

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

Subtask #1

0.0 / 1.0

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