| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
588K 0ms 1次AC#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
using namespace std;
int X[202], Y[202];
const double PI = 3.141592654;
double angle(int idx1, int idx2){
if(X[idx1] == X[idx2]){
if(Y[idx1] < Y[idx2]) return PI/2;
else return PI*3/2;
}
if(Y[idx1] == Y[idx2]){
if(X[idx1] < X[idx2]) return 0;
else return PI;
}
double k = atan((Y[idx2] + 0.0 - Y[idx1]) / (X[idx2] + 0.0 - X[idx1]));
if(k < 0) k += PI;
if(Y[idx1] < Y[idx2]) return k;
return k+PI;
}
double rotAngle(int idx1, int idx2, int idx3){
double h = angle(idx2, idx1) - angle(idx2, idx3);
if(h <= 0) h += 2*PI;
return h;
}
void quickSort(int s[], int l, int r, int curIdx)
{
if (l < r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && angle(curIdx, s[j]) <= angle(curIdx, x))//s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && angle(curIdx, s[i]) > angle(curIdx, x))//s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1, curIdx); // 递归调用
quickSort(s, i + 1, r, curIdx);
}
}
int main() {
int M;
scanf("%d", &M);
for(int ii = 0; ii < M; ii++){
int N;
scanf("%d", &N);
bool adj[202][202] = {false};
int adjList[202][202];
int adjNum[202] = {0};
for(int i = 0; i < N; i++){
int I, deg;
scanf("%d", &I);
scanf("%d%d%d", X+I, Y+I, °);
for(int j = 0; j < deg; j++){
int temp;
scanf("%d", &temp);
adj[I][temp] = true;
adjList[I][adjNum[I]] = temp;
adjNum[I] ++;
}
}
for(int i = 1; i <= N; i++){
quickSort(adjList[i], 0, adjNum[i]-1, i);
}
int adjIdx[202][202];
for(int i = 1; i <= N; i++){
for(int j = 0; j < adjNum[i]; j++){
adjIdx[i][adjList[i][j]] = j;
}
}
int propNum[202] = {0};
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(!adj[i][j]) continue;
bool proper = true;
bool used[202] = {false};
double njh = 0;
int sides = 1;
int i1 = i, i2 = j;
used[i] = true;
//used[j] = true;
adj[i][j] = false;
while(1){
//cout << i1 << " " << i2 << endl;
//system("PAUSE");
int idxofi1 = adjIdx[i2][i1];
int idxofi3 = (idxofi1 + 1) % adjNum[i2];
int i3 = adjList[i2][idxofi3];
if(proper) njh += rotAngle(i1,i2,i3);
adj[i2][i3] = false;
if(i2 == i && i3 == j) break;
if(used[i2]){
proper = false;
}
used[i2] = true;
sides ++;
i1 = i2;
i2 = i3;
}
if(proper && abs(njh - (sides-2)*PI) < 1e-4){
propNum[sides] ++;
}
}
}
int k;
scanf("%d", &k);
cout << propNum[k] << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator