程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3525 半面交+二分

poj3525 半面交+二分

編輯:C++入門知識

//題目意思:求在一個形狀為多邊形的島中的一點到海的最大距離
//解題思路:
//有一種方法:二分距離,再求半面交
//這裡需要注意的是精度問題,長度要從0~10^9二分(好像很多對長度的二分都是10^9的),eps 1e-11
//212K 32ms 代碼如下:

[cpp] 
#include<iostream> 
#include<cstdio> 
#include<math.h> 
#define eps 1e-11 
using namespace std; 
const int MAXN=202; 
struct point {double x,y;}; 
point points[MAXN],p[MAXN],q[MAXN]; 
int n; 
bool zero(double x) 

 return x>0? x<eps:x>-eps; 

double xmult(point p1,point p2,point p0) 

 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 

int same_side(point p1,point p2,point l1,point l2) 

 return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps; 

point intersection(point p1,point p2,point p3,point p4) 

 point ret=p1; 
 double t=((p1.x-p3.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p3.y)) 
  /((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y)); 
 ret.x+=t*(p2.x-p1.x); 
 ret.y+=t*(p2.y-p1.y); 
 return ret; 

void polygon_cut(int &n,point *p,point l1,point l2,point side) 

 point pp[1000]; 
 int m=0,i; 
 for(i=0;i<n;i++) 
 { 
  if(same_side(p[i],side,l1,l2)) 
   pp[m++]=p[i]; 
  if(!same_side(p[i],p[(i+1)%n],l1,l2) 
   &&!(zero(xmult(p[i],l1,l2)) 
   &&zero(xmult(p[(i+1)%n],l1,l2)))) 
   pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2); 
 } 
 n=0; 
 for(i=0;i<m;i++) 
  if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y)) 
   p[n++]=pp[i]; 
  if(zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y)) 
   n--;// 
   
   

double distance(point p1,point p2) 

 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 

void slove(double dis,int &m) 

 int i; 
 for(i=0;i<n;i++) 
 { 
  point side; 
  //向內推進dis 
  point s=points[i],e=points[(i+1)%n]; 
  double xx=e.x-s.x,yy=e.y-s.y; 
  double dd=sqrt(xx*xx+yy*yy); 
  s.x+=dis*(-yy)/dd; 
  s.y+=dis*(xx)/dd; 
  e.x+=dis*(-yy)/dd; 
  e.y+=dis*(xx)/dd; 
  side.x=s.x-yy; 
  side.y=s.y+xx; 
  polygon_cut(m,p,s,e,side); 
 } 

double two(double l,double r) 

 double mid=(l+r)/2.0; 
 if(r-l<eps)return mid; 
 int i; 
 for(i=0;i<n;i++)p[i]=points[i]; 
 int m=n; 
 slove(mid,m); 
 if(m<3)return two(l,mid); 
 else 
 { 
  return two(mid,r); 
 } 

int main() 

 while(scanf("%d",&n),n) 
 { 
  int i; 
  for(i=0;i<n;i++) 
  { 
   scanf("%lf%lf",&points[i].x,&points[i].y); 
  } 
  double res=0.0; 
  res=two(0,1000000000); 
  printf("%.6lf\n",res); 
 } 
 return 0; 


作者:ssslpk

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved