|
|
Posted on 2010-09-27 02:23 Uriel 阅读(397) 评论(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;
}
|