|
|
Posted on 2009-11-10 19:15 Uriel 閱讀(289) 評論(0) 編輯 收藏 引用 所屬分類: POJ 、 計算幾何
真是挺水的一題。。以為有什么神奇的規(guī)律，看Discuss說坐標(biāo)轉(zhuǎn)換就使勁往那方面想。。一天多無果。。
然后O(n^3)暴力切掉。。
貼個代碼。。紀念為了找規(guī)律草稿紙上N種坐標(biāo)系的圖。。
  /**//*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;
}
|