|
Posted on 2009-11-10 19:15 Uriel 阅读(277) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 计算几何
真是挺水的一题。。以为有什么神奇的规律,看Discuss说坐标转换就使劲往那方面想。。一天多无果。。 然后O(n^3)暴力切掉。。 贴个代码。。纪念为了找规律草稿纸上N种坐标系的图。。
 /**//*Problem: 1244 User: Uriel
Memory: 784K Time: 16MS
Language: G++ Result: Accepted*/

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct point
  {
double x[1000];
double y[1000];
};

point P[27];
char s;
int i,j,k,h,layer,sum[27];
bool res;

double Dis(int x,int a,int b)
  {
return sqrt((P[x].x[a]-P[x].x[b])*(P[x].x[a]-P[x].x[b])+(P[x].y[a]-P[x].y[b])*(P[x].y[a]-P[x].y[b]));
}

bool Equal(double a,double b)
  {
return fabs(a-b)<0.0001;
}

int main()
  {
while(1)
 {
memset(sum,0,sizeof(sum));
memset(P,0x00,sizeof(P));
res=false;
scanf("%d",&layer);
if(!layer)break;
getchar();
for(i=1;i<=layer;++i)
 {
for(j=1;j<=i;j++)
 {
scanf("%c",&s);
P[s-'a'].x[sum[s-'a']]=-i-1+2*j;
P[s-'a'].y[sum[s-'a']]=sqrt(3.0)*(layer-i);
sum[s-'a']++;
}
}
i=0;
flag: if(i<26)
 {
for(j=0;j<sum[i]-2;j++)
 {
for(k=j+1;k<sum[i]-1;k++)
 {
for(h=k+1;h<sum[i];h++)
 {
if(Equal(Dis(i,j,k),Dis(i,k,h))&&Equal(Dis(i,j,h),Dis(i,k,h))&&Equal(Dis(i,j,h),Dis(i,k,h)))
 {
printf("%c",i+'a');
res=true;
i++;
goto flag;
}
}
}
}
i++;
goto flag;
}
if(!res)
 {
printf("LOOOOOOOOSER!\n");
}
else
 {
printf("\n");
}
}
system("PAUSE");
return 0;
}

|