Submission #9142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9142	2014-09-28T03:25:13 Z	effserv	Wall construction (kriii2_WA)	C++	4 / 4	96 ms	5712 KB

WA

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

using namespace std;

#define maxS	1001

typedef pair <int, int> point;

typedef struct _node
{
	int i;
	int a;
	int b;
	int c;
	int d;
	bool det;
}node;

node nn[maxS];
int x[maxS], y[maxS];

vector <int> one[maxS], two[maxS], three[maxS], four[maxS];

int cmp1(node i, node j)
{
	if (i.det == true && j.det == true)
	{
		return i.i < j.i;
	}
	
	return i.det > j.det;
}

int IsCandidate(point bp, point cp, point ap)
{
	point p1(cp.first - bp.first, cp.second - bp.second);
	point p2(ap.first - bp.first, ap.second - bp.second);

	return p2.second*p1.first - p1.second*p2.first;
}

double dist(point ap1, point ap2)
{
	return hypot(ap2.first - ap1.first, ap2.second - ap1.second);
}

vector <point> points;


int main()
{
//	freopen("input.txt", "r", stdin);
	int n,r;
	scanf("%d%d", &n, &r);
	
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &x[i], &y[i]);
		nn[i].det = true;
	}

	for (int i = 0; i < n; i++)
	{
		nn[i].i = i;

		int a = 0;
		int b = 0;
		int c = 0;
		int d = 0;

		for (int j = 0; j < n; j++)
		{
			if (i == j || nn[j].det == false)
				continue;

			if (x[j] - x[i] >= 0 && y[j] - y[i] >= 0)
			{
				a++;
				one[nn[i].i].push_back(j);
			}
			if (x[j] - x[i] <= 0 && y[j] - y[i] >= 0)
			{
				b++;
				two[nn[i].i].push_back(j);
			}
			if (x[j] - x[i] <= 0 && y[j] - y[i] <= 0)
			{
				c++;
				three[nn[i].i].push_back(j);
			}
			if (x[j] - x[i] >= 0 && y[j] - y[i] <= 0)
			{
				d++;
				four[nn[i].i].push_back(j);
			}

			if (a && b && c && d)
			{
				nn[i].det = false;
				break;
			}
		}

		nn[i].a = a;
		nn[i].b = b;
		nn[i].c = c;
		nn[i].d = d;
	}

	sort(nn, nn + n, cmp1);

	for (int i = 0; i < n; i++)
	{
//		printf("x : %d y : %d\n", x[nn[i].i], y[nn[i].i]);
//		printf("1사 : %d 2사 : %d 3사 : %d 4사 : %d\n", nn[i].a, nn[i].b, nn[i].c, nn[i].d);
		if (nn[i].det == false)
		{
			n = i;
//			printf("새로 바뀐 n 은 : %d\n", n);
			break;

		}
	}

	for (int i = 0; i < n; i++)
	{
		bool onedet = nn[i].a ? false : true;
		bool twodet = nn[i].b ? false : true;
		bool thrdet = nn[i].c ? false : true;
		bool fourdet = nn[i].d ? false : true;

		if (onedet == true && twodet == true)
			continue;
		if (onedet == true && fourdet == true)
			continue;
		if (twodet == true && thrdet == true)
			continue;
		if (thrdet == true && fourdet == true)
			continue;

		if (onedet == false && thrdet == false)
		{
			int onesz = one[nn[i].i].size();
			int thrsz = three[nn[i].i].size();

			bool twodet2 = false;
			bool fourdet2 = false;
			bool otherdet = false;

			for (int j = 0; j < onesz; j++)
			{
				int tmp = one[nn[i].i][j];

				for (int k = 0; k < thrsz; k++)
				{
					int dx = x[tmp] + x[three[nn[i].i][k]] - 2 * x[nn[i].i];
					int dy = y[tmp] + y[three[nn[i].i][k]] - 2 * y[nn[i].i];

					if (dx <= 0 && dy >= 0)
						twodet2 = true;
					else if (dx >= 0 && dy <= 0)
						fourdet2 = true;
					else
						otherdet = true;
				}
				if (twodet2 == true && fourdet2 == true)
				{
					nn[i].det = false;
					break;
				}
			}

			if (twodet2 == false && fourdet2 == false)
			{
				if (otherdet == true)
				{
					nn[i].det = false;
				}
				else
				{
					printf("오류\n");
					return 0;
				}
			}

		}

		if (twodet == false && fourdet == false)
		{
			int twosz = two[nn[i].i].size();
			int foursz = four[nn[i].i].size();

			bool onedet2 = false;
			bool thrdet2 = false;
			bool otherdet = false;

			for (int j = 0; j < twosz; j++)
			{
				int tmp = two[nn[i].i][j];

				for (int k = 0; k < foursz; k++)
				{
					int dx = x[tmp] + x[four[nn[i].i][k]] - 2 * x[nn[i].i];
					int dy = y[tmp] + y[four[nn[i].i][k]] - 2 * y[nn[i].i];

					if (dx >= 0 && dy >= 0)
						onedet2 = true;
					else if (dx <= 0 && dy <= 0)
						thrdet2 = true;
					else
						otherdet = true;
				}
				if (onedet2 == true && thrdet2 == true)
				{
					nn[i].det = false;
					break;
				}
			}

			if (onedet2 == false && thrdet2 == false)
			{
				if (otherdet == true)
				{
					nn[i].det = false;
				}
				else
				{
					printf("오류\n");
					return 0;
				}
			}
		}

	}

	sort(nn, nn + n, cmp1);

	for (int i = 0; i < n; i++)
	{
//		printf("x : %d y : %d\n", x[nn[i].i], y[nn[i].i]);
//		printf("1사 : %d 2사 : %d 3사 : %d 4사 : %d\n", nn[i].a, nn[i].b, nn[i].c, nn[i].d);
		if (nn[i].det == false)
		{
			n = i;
//			printf("새로 바뀐 n 은 : %d\n", n);
			break;

		}
	}

	int minXi = -1, minX = 10000000;

	for (int i = 0; i < n; i++)
	{
		points.push_back(point(x[nn[i].i], y[nn[i].i]));
		if (minX > x[nn[i].i])
		{
			minX = x[nn[i].i];
			minXi = i;
		}
	}

	vector <point> boundary;
	boundary.push_back(point(points[minXi].first, points[minXi].second));

	double res = 0;
	while (1)
	{
		point bp = boundary.back();
		point cp = points[0];

		for (int i = 0; i < n; i++)
		{
		//	if (bp == points[i])
			//	continue;
	//		printf("%d point x : %d y : %d\n",i,points[i].first, points[i].second);
	//		printf("%d cp x : %d y : %d\n", i, cp.first, cp.second);
			int det = IsCandidate(bp, cp, points[i]);
	//		printf("%d\n", det);

			if (det < 0 || (det == 0 && (dist(points[i], bp) > dist(cp,bp)) ))
			{
		//		printf("%d %d\n", points[i].first, points[i].second);
				cp = points[i];
			}
		}

		res += dist(cp, bp);

		if (cp == boundary[0])
			break;
		boundary.push_back(cp);
	}

	printf("%lf\n", res + (2 * acos(0.0)*2 *r));

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1356 KB	Output is correct
2	Correct	0 ms	1356 KB	Output is correct
3	Correct	0 ms	1356 KB	Output is correct
4	Correct	0 ms	1356 KB	Output is correct
5	Correct	0 ms	1356 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1356 KB	Output is correct
2	Correct	0 ms	1356 KB	Output is correct
3	Correct	0 ms	1356 KB	Output is correct
4	Correct	0 ms	1356 KB	Output is correct
5	Correct	0 ms	1356 KB	Output is correct
6	Correct	0 ms	1488 KB	Output is correct
7	Correct	72 ms	5580 KB	Output is correct
8	Correct	96 ms	5712 KB	Output is correct
9	Correct	0 ms	1488 KB	Output is correct
10	Correct	0 ms	1488 KB	Output is correct
11	Correct	0 ms	1356 KB	Output is correct
12	Correct	0 ms	1356 KB	Output is correct
13	Correct	0 ms	1356 KB	Output is correct
14	Correct	0 ms	1356 KB	Output is correct
15	Correct	0 ms	1356 KB	Output is correct
16	Correct	0 ms	1356 KB	Output is correct
17	Correct	0 ms	1488 KB	Output is correct
18	Correct	0 ms	1356 KB	Output is correct
19	Correct	0 ms	1356 KB	Output is correct
20	Correct	0 ms	1356 KB	Output is correct