|
Posted on 2009-11-10 19:15 Uriel 阅读(271) 评论(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; }
|