題目要求統計一個平面圖中所有邊數為k的面的個數。應該是個經典問題。說說我的算法吧。
枚舉每條邊，做以下的基本步驟。
基本步驟：以這條邊作起始邊，不斷地找下一條“最左轉”的邊，并且標記每個點的訪問次數，直到某個點第3次被訪問為止。
經過這個步驟之后，得到一個頂點序列。容易知道，當且僅當這個頂點序列是2-重復（就是形如12341234這樣），并且是逆時針旋轉的，那么就是一個面。
接下去我們就把所有找到的邊數為k面進行hash去重，就得到答案啦。
貌似我想的這個算法不夠好，如果有更好的算法，歡迎和我討論。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-7 16:26:27
File Name: pku1092.cpp
Description:
************************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 210;
const int prime = 502973;
typedef struct point_t
{
int x, y, id;
int cnt_child;
int child[maxn];
};
typedef struct farmland_t
{
int cnt;
int v[maxn];
};
typedef struct hash_t
{
farmland_t farmland;
hash_t *next;
};
int n, size;
point_t point[maxn];
hash_t *hash[prime];
int operator ==(const farmland_t &a, const farmland_t &b)
{
if (a.cnt != b.cnt)
return 0;
for (int i = 0; i < a.cnt; i++)
if (a.v[i] != b.v[i])
return 0;
return 1;
}
int hash_insert(const farmland_t &farmland)
{
unsigned int key = 1;
for (int i = 0; i < farmland.cnt; i++)
key *= farmland.v[i];
key %= prime;
for (hash_t *t = hash[key]; t; t = t->next)
if (t->farmland == farmland)
return 0;
hash_t *t = new hash_t;
t->farmland = farmland;
t->next = hash[key];
hash[key] = t;
return 1;
}
int dot_mul(const point_t &a, const point_t &b)
{
return a.x * b.x + a.y * b.y;
}
int cross_mul(const point_t &a, const point_t &b)
{
return a.x * b.y - a.y * b.x;
}
point_t operator -(const point_t &a, const point_t &b)
{
point_t ret;
ret.x = a.x - b.x;
ret.y = a.y - b.y;
return ret;
}
double len(const point_t &a)
{
return sqrt(double(a.x * a.x + a.y * a.y));
}
double angle_a_to_b(const point_t &a, const point_t &b)
{
double ret = acos(dot_mul(a, b) / (len(a) * len(b)));
int cross = cross_mul(a, b);
if (cross == 0)
return 0.0;
else if (cross > 0)
return -ret;
else
return ret;
}
int find_farmland(int a, int b, farmland_t &farmland)
{
int stack[maxn * 2];
int top = 2;
stack[0] = a;
stack[1] = b;
int used[maxn];
memset(used, 0, sizeof(used));
used[a] = used[b] = 1;
while (1)
{
double min_angle = 1e10;
int min_i;
for (int i = 0; i < point[stack[top - 1]].cnt_child; i++)
{
int p = point[stack[top - 1]].child[i];
if (p == stack[top - 2])
continue;
double angle = angle_a_to_b(point[stack[top - 1]] - point[stack[top - 2]], point[p] - point[stack[top - 1]]);
if (angle < min_angle)
{
min_angle = angle;
min_i = p;
}
}
if (used[min_i] == 2)
{
if (min_i != a)
return 0;
if (top & 1)
return 0;
if (top / 2 != size)
return 0;
for (int i = 0; i < top / 2; i++)
if (stack[i] != stack[i + top / 2])
return 0;
int area = 0;
for (int i = 0; i < top / 2; i++)
area += cross_mul(point[stack[i]], point[stack[i + 1]]);
if (area <= 0)
return 0;
{
farmland.cnt = top / 2;
int min = maxint;
int mini;
for (int i = 0; i < top / 2; i++)
if (stack[i] < min)
{
min = stack[i];
mini = i;
}
for (int i = 0; i < top / 2; i++)
farmland.v[i] = stack[mini + i];
return 1;
}
}
else
{
used[min_i]++;
stack[top++] = min_i;
}
}
}
int count_farmland()
{
memset(hash, 0, sizeof(hash));
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < point[i].cnt_child; j++)
{
farmland_t farmland;
int flag = find_farmland(i, point[i].child[j], farmland);
if (flag)
if (hash_insert(farmland))
cnt++;
}
return cnt;
}
int main()
{
int ca;
for (scanf("%d", &ca); ca--;)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d%d", &point[i].id, &point[i].x, &point[i].y, &point[i].cnt_child);
for (int j = 0; j < point[i].cnt_child; j++)
scanf("%d", &point[i].child[j]);
}
scanf("%d", &size);
printf("%d\n", count_farmland());
}
return 0;
}