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

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

Re: 11769 - All Souls Night

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] - A[c];
double ay = A[a] - A[c];
double az = A[a] - A[c];

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

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] - A[a];
double vy = A[i] - A[a];
double vz = A[i] - A[a];

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];
double ay = A[a];
double az = A[a];

double bx = A[b];
double by = A[b];
double bz = A[b];

double cx = A[c];
double cy = A[c];
double cz = A[c];

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], &A[i], &A[i]);

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 = 10; // this is to prevent optimizer from ignoring variable A as unused.
A += A;
}
}

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