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 1851 Map---计算几何

Posted on 2010-09-27 02:23 Uriel 阅读(417) 评论(0)  编辑 收藏 引用 所属分类: POJ计算几何
        ECUST ACHunter威武,今天哈尔滨现场赛一度rank6(算上旅游队),后2h可惜了,福州继续加油~~        

        继续刷计算几何。。不会的题目越来越多。。总算翻到个大水题,不过AC不足100,不知为何。。

        看完题发现大水,兴奋地敲完之后发现题目给的半径完全没用到,想了下,果然脑残。。有可能走出island那个圆的范围了。。于是各种特判。。一交,WA。仔细检查了下。。果然变量名敲错一个字母,改了之后A了。。Ctrl+C,Ctrl+V的后果是。。好长好长的代码。。

        这题是POJ 1000AC,还是这么菜,继续努力 && 祈祷现场赛好运

        其他没碰到trick,留下丑陋的代码一份供后来者对拍。。思路还不清楚的可以参考Discuss~

//Problem: 1851  User: Uriel 
//Memory: 180K  Time: 16MS 
//Language: C++  Result: Accepted 

#include
<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#define eps 1e-10

struct point{
    
double x,y;
}
s,e;

double r;

bool in_circle(double x,double y){
    
if(x*x+y*y-r*r<eps)return true;
    
return false;
}


int main(){
    
while(scanf("%lf",&r),fabs(r+1.0)>eps){
        scanf(
"%lf %lf %lf %lf",&s.x,&s.y,&e.x,&e.y);
        
if(fabs(s.x-e.x)<eps){
            
if(s.y-e.y<-eps)printf("north %.10lf\n",e.y-s.y);
            
else
                printf(
"south %.10lf\n",s.y-e.y);
            puts(
"");
            
continue;
        }

        
if(fabs(s.y-e.y)<eps){
            
if(s.x-e.x<-eps)printf("east %.10lf\n",e.x-s.x);
            
else
                printf(
"west %.10lf\n",s.x-e.x);
            puts(
"");
            
continue;
        }

        
//case 1
        if(s.x-e.x<-eps && s.y-e.y<-eps){
            
if((e.x-s.x)-(e.y-s.y)<-eps){
                
if(in_circle(s.x,s.y+(e.y-s.y)-(e.x-s.x))){
                    printf(
"north %.10lf\n",(e.y-s.y)-(e.x-s.x));
                    printf(
"northeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
                }

                
else{
                    printf(
"northeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
                    printf(
"north %.10lf\n",(e.y-s.y)-(e.x-s.x));
                }

            }

            
else if(fabs((e.x-s.x)-(e.y-s.y))<eps){
                printf(
"northeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
            }

            
else{
                
if(in_circle(s.x+(e.x-s.x)-(e.y-s.y),s.y)){
                    printf(
"east %.10lf\n",(e.x-s.x)-(e.y-s.y));
                    printf(
"northeast %.10lf\n",sqrt(2.0)*(e.y-s.y));
                }

                
else{
                    printf(
"northeast %.10lf\n",sqrt(2.0)*(e.y-s.y));
                    printf(
"east %.10lf\n",(e.x-s.x)-(e.y-s.y));
                }

            }

            puts(
"");
            
continue;
        }

        
//case 2
        if(e.x-s.x<-eps && e.y-s.y>eps){
            
if((s.x-e.x)-(e.y-s.y)<-eps){
                
if(in_circle(s.x,s.y+(e.y-s.y)-(s.x-e.x))){
                    printf(
"north %.10lf\n",(e.y-s.y)-(s.x-e.x));
                    printf(
"northwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
                }

                
else{
                    printf(
"northwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
                    printf(
"north %.10lf\n",(e.y-s.y)-(s.x-e.x));
                }

            }

            
else if(fabs((s.x-e.x)-(e.y-s.y))<eps){
                printf(
"northwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
            }

            
else{
                
if(in_circle(s.x-(s.x-e.x)+(e.y-s.y),s.y)){
                    printf(
"west %.10lf\n",(s.x-e.x)-(e.y-s.y));
                    printf(
"northwest %.10lf\n",sqrt(2.0)*(e.y-s.y));
                }

                
else{
                    printf(
"northwest %.10lf\n",sqrt(2.0)*(e.y-s.y));
                    printf(
"west %.10lf\n",(s.x-e.x)-(e.y-s.y));
                }

            }

            puts(
"");
            
continue;
        }

        
//case 3
        if(s.x-e.x>eps && s.y-e.y>eps){
            
if((s.x-e.x)-(s.y-e.y)<-eps){
                
if(in_circle(s.x,s.y-(s.y-e.y)+(s.x-e.x))){
                    printf(
"south %.10lf\n",(s.y-e.y)-(s.x-e.x));
                    printf(
"southwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
                }

                
else{
                    printf(
"southwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
                    printf(
"south %.10lf\n",(s.y-e.y)-(s.x-e.x));
                }

            }

            
else if(fabs((s.x-e.x)-(s.y-e.y))<eps){
                printf(
"southwest %.10lf\n",sqrt(2.0)*(s.x-e.x));
            }

            
else{
                
if(in_circle(s.x-(s.x-e.x)+(s.y-e.y),s.y)){
                    printf(
"west %.10lf\n",(s.x-e.x)-(s.y-e.y));
                    printf(
"southwest %.10lf\n",sqrt(2.0)*(s.y-e.y));
                }

                
else{
                    printf(
"southwest %.10lf\n",sqrt(2.0)*(s.y-e.y));
                    printf(
"west %.10lf\n",(s.x-e.x)-(s.y-e.y));
                }

            }

            puts(
"");
            
continue;
        }

        
//case 4
        if(e.x-s.x>eps && e.y-s.y<-eps){
            
if((e.x-s.x)-(s.y-e.y)<-eps){
                
if(in_circle(s.x,s.y-(s.y-e.y)+(e.x-s.x))){
                    printf(
"south %.10lf\n",(s.y-e.y)-(e.x-s.x));
                    printf(
"southeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
                }

                
else{
                    printf(
"southeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
                    printf(
"south %.10lf\n",(s.y-e.y)-(e.x-s.x));
                }

            }

            
else if(fabs((e.x-s.x)-(s.y-e.y))<eps){
                printf(
"southeast %.10lf\n",sqrt(2.0)*(e.x-s.x));
            }

            
else{
                
if(in_circle(s.x+(e.x-s.x)-(s.y-e.y),s.y)){
                    printf(
"east %.10lf\n",(e.x-s.x)-(s.y-e.y));
                    printf(
"southeast %.10lf\n",sqrt(2.0)*(s.y-e.y));
                }

                
else{
                    printf(
"southeast %.10lf\n",sqrt(2.0)*(s.y-e.y));
                    printf(
"east %.10lf\n",(e.x-s.x)-(s.y-e.y));
                }

            }

            puts(
"");
            
continue;
        }

    }

    
return 0;
}





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