|
|
Posted on 2010-09-27 02:23 Uriel 閱讀(441) 評論(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;
}
|