Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1244 Slots of Fun---几何

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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理