【2016-CCPC-H】计算几何(Special Tetrahedron,hdu 5839)

时间:2023-02-10 18:48:41

http://www.cnblogs.com/Sunshine-tcf/p/5770545.html


本来暴力枚举O(n^4)铁定超时的。

但是这种方法枚举得很有技巧。

前两层是暴力枚举,

第三层筛选,第四层在筛选的结果中枚举。

前三层是O(n^3),

第四层在筛选出来的点中枚举,枚举量十分小,可以理解为常数极小的O(n^4)。

还要考虑清楚各种情况下重复或错误的枚举。

四点共面的判断等。

此题非常值得学习。

要学会抓住题目的特殊信息。

比如:这个四边形的要求为何是这样的,而不是随便的?是不是因为这样就可以用特殊的方法枚举?


#include<bits/stdc++.h>
#define maxn 220
using namespace std;

int n;

struct pt
{
int x,y,z;
};
pt p[maxn];

int dist(int a1,int a2)
{
pt a=p[a1];
pt b=p[a2];
int x=a.x-b.x;
int y=a.y-b.y;
int z=a.z-b.z;
return x*x+y*y+z*z;
}

pt xl(pt a,pt b)
{
pt c;
c.x=b.x-a.x;
c.y=b.y-a.y;
c.z=b.z-a.z;
return c;
}

pt cx(pt a,pt b)
{
pt c;
c.x=a.y*b.z-a.z*b.y;
c.y=a.z*b.x-a.x*b.z;
c.z=a.x*b.y-a.y*b.x;
return c;
}

bool gm(int a1,int a2,int a3,int a4)
{
pt a,b,c,d;
a=p[a1];
b=p[a2];
c=p[a3];
d=p[a4];
pt ac,ad,bc,bd;
ac=xl(a,c);
ad=xl(a,d);
bc=xl(b,c);
bd=xl(b,d);
pt xl1=cx(ac,ad);
pt xl2=cx(bc,bd);
pt ans=cx(xl1,xl2);
if(ans.x==0&&ans.y==0&&ans.z==0) return true;
else return false;
}

int main()
{
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++)
{
int cnt=0;
int zheng=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
vector<int>vec;
for(int k=1;k<=n;k++)
{
if(k==i||k==j) continue;
if(dist(i,k)==dist(j,k)) vec.push_back(k);
}
for(unsigned int u=0;u<vec.size();u++)
for(unsigned int v=u+1;v<vec.size();v++)
if(dist(i,vec[u])==dist(i,vec[v]))
{
if(gm(i,j,vec[u],vec[v])) continue;
cnt++;
if(dist(i,j)==dist(vec[u],vec[v])&&dist(i,j)==dist(i,vec[u]))
zheng++;
}
}
printf("Case #%d: %d\n",t,cnt/2-zheng/3);
}
return 0;
}