11769 - All Souls Night

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
zholnin
New poster
Posts: 8
Joined: Thu Aug 21, 2014 12:03 am

Re: 11769 - All Souls Night

Post by zholnin » Tue Sep 29, 2015 9:42 pm

Hello,

I have strong reasons to believe that some of the test input violates the following:

"They will be positioned in such a way that there won't be more than 3 souls in any polygonal face of the veil."

I struggled with this problem for hours and, though my code produced exactly the same output as uDebug over thousands of testcases, UVA continued to say "WA". So I tried to investigate if there are any testcases with more then 3 coplanar point. I think I found it. The idea of the test is the following:

1. In convex hull, if there are no more then 3 coplanar points, every edge will included in only two triangles belonging to convex hull.
2. If there are 4 coplanar points, then there can be more then two triangles - actually there will be three triangles belonging to convex hull.

So I tried to detect it. "vector<int> A = vector<int>(10000000000);" is my ugly way to cause runtime error in case this situation is detected and this is when I got runtime error instead of WA.

Now I'll try to change my code to take care of situation with 4 and more coplanar points.

Here is the code:

Code: Select all

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <list>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <map>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <assert.h>
#include <bitset>

using namespace std;
vector<vector<double>> A;

bool TestFace(int a, int b, int c)
{
	double ax = A[a][0] - A[c][0];
	double ay = A[a][1] - A[c][1];
	double az = A[a][2] - A[c][2];

	double bx = A[b][0] - A[c][0];
	double by = A[b][1] - A[c][1];
	double bz = A[b][2] - A[c][2];

	double nx =   ay * bz - by * az;
	double ny = - ax * bz + bx * az;
	double nz =   ax * by - bx * ay;

	int positive = 0;
	for (int i = 0; i < A.size(); i++)
	{
		if (i == a || i == b || i == c) continue;
		double vx = A[i][0] - A[a][0];
		double vy = A[i][1] - A[a][1];
		double vz = A[i][2] - A[a][2];

		double dp = vx * nx + vy * ny + vz * nz;
		if (positive == 0) positive = dp > 0 ? 1 : -1;
		if (dp * positive < 0) return false;
	}
	return true;
}

double surface(int a, int b, int c)
{
	double ax = A[a][0];
	double ay = A[a][1];
	double az = A[a][2];

	double bx = A[b][0];
	double by = A[b][1];
	double bz = A[b][2];

	double cx = A[c][0];
	double cy = A[c][1];
	double cz = A[c][2];

	double l1 = sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by) + (az - bz) * (az - bz));
	double l2 = sqrt((ax - cx) * (ax - cx) + (ay - cy) * (ay - cy) + (az - cz) * (az - cz));
	double l3 = sqrt((bx - cx) * (bx - cx) + (by - cy) * (by - cy) + (bz - cz) * (bz - cz));

	double p2 = (l1 + l2 + l3) / 2.0;

	return sqrt(p2 * (p2 - l1) * (p2 - l2) * (p2 - l3));
}

int main()
{
	clock_t start = clock();
	for (int tc = 1; ; tc++)
	{
		int n;
		scanf("%d", &n);

		if (n == 0) break;

		A = vector<vector<double>>(n, vector<double>(3));

		for (int i = 0; i < n; i++)
			scanf("%lf %lf %lf", &A[i][0], &A[i][1], &A[i][2]);

		if (n == 3)
		{
			printf("Case %d: 0.0\n", tc);
			continue;
		}

		map<pair<int, int>, int> M; // this is to count number of triangles for each edge

		double ans = 0.0;
		for (int f1 = 0; f1 < n; f1++)
		for (int f2 = f1 + 1; f2 < n; f2++)
		for (int f3 = f2 + 1; f3 < n; f3++)
		{

			if (TestFace(f1, f2, f3))
			{
				M[{f1, f2}]++; // every edge gets +1 triangle
				M[{f2, f3}]++;
				M[{f1, f3}]++;
				ans += surface(f1, f2, f3);
			}
		}

		for (auto j = M.begin(); j != M.end(); j++)
		{
			if (j->second != 2)
			{
				vector<int> A = vector<int>(10000000000); //runtime error
				A[100] = 10; // this is to prevent optimizer from ignoring variable A as unused.
				A[200] += A[100];
			}
		}

		printf("Case %d: %.2lf\n", tc, ans + 1e-7);
	}
}


Post Reply

Return to “Volume 117 (11700-11799)”