K - Cross Spider
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87794#problem/K
Description
Input
The first line of the input contains an integer n (1 ¬ n ¬ 100 000). The following n lines contain a description of the flies in a 3D space: the i-th line contains three integers xi , yi , zi (−1 000 000 ¬ xi ; yi ; zi ¬ 1 000 000) giving the coordinates of the i-th fly (a point in a 3-dimensional Euclidean space). No two flies are located in the same point.
Output
Your program should output a single word TAK (i.e., yes in Polish) if the spider can catch all the flies with a single spiderweb. Otherwise your program should output the word NIE (no in Polish).
Sample Input
4 0 0 0 -1 0 -100 100 0 231 5 0 15
Sample Output
TAK
HINT
题意
一个三维空间，给n个点，问着n个点是否在同一个平面上
题解：
首先先找到不在同一条直线上的三个点，做法向量，然后我们再枚举任意两个点，如果这两个点是和法向量垂直的话，就说明在一个平面上
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
#include <list>
#include <bitset>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin)
#define pi acos(-1) using namespace std; typedef struct point
{
long long x , y , z;
}; const int maxn = 1e5 + ;
const double eps = 1e-;
int n ;
point A[maxn];
point vi; bool judge(point a,point b)
{
return a.x * b.y == b.x * a.y && a.y*b.z == b.y*a.z && a.x * b.z == a.z*b.x;
} int main(int argc,char *argv[])
{
scanf("%d",&n);
for(int i = ; i < n ; ++ i) scanf("%I64d%I64d%I64d",&A[i].x,&A[i].y,&A[i].z);
if (n <= )
{
printf("TAK\n");
return ;
}
else
{
int ok = ;
for(int i = ; i < n ; ++ i)
{
int a = i ;
int b = (i+) % n;
int c = (i+) % n;
point vi1 , vi2;
vi1.x = A[b].x - A[a].x;
vi1.y = A[b].y - A[a].y;
vi1.z = A[b].z - A[a].z;
vi2.x = A[c].x - A[b].x;
vi2.y = A[c].y - A[b].y;
vi2.z = A[c].z - A[b].z;
if (judge(vi1,vi2)) continue;
else
{
vi.x = vi1.y*vi2.z - vi2.y*vi1.z;
vi.y = vi2.x*vi1.z - vi1.x*vi2.z;
vi.z = vi1.x*vi2.y - vi1.y*vi2.x;
ok = ;
break;
}
}
if (ok)
{
printf("TAK\n");
return ;
}
else
{
ok = ;
for(int i = ; i < n ; ++ i)
{
int a = i ;
int b = (i+) % n;
point tx;
tx.x = A[b].x - A[a].x;
tx.y = A[b].y - A[a].y;
tx.z = A[b].z - A[a].z;
if (vi.x * tx.x + vi.y * tx.y + vi.z * tx.z != )
{
ok = ;
break;
}
}
}
if (ok) printf("TAK\n");
else printf("NIE\n");
return ;
}
return ;
}