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);
}
}