注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2540 Hotter Colder 半平面交 不等式求区域面积  

2011-05-09 12:09:35|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在一个区间内寻找某一个点,每次走法会提示距目标是更近、更远还是相同。每次可确定一个目标必在的区域,求这个区域的面积。
 假定寻找者从A点走到B点,做线段AB的中垂线,取距目标近的那一半。用半平面交即可求该区域。
注意Same时区域面积为0;
若有出现面积为0,则之后的都是0;
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
const double eps = 1e-10;
int sz;
double flag;
struct point
{
double x,y;
}p[60],q[60];
void init()
{    
sz = 4;
p[1].x=p[1].y=0;
p[2].x=10, p[2].y=0;    
p[3].x=p[3].y=10;    
p[4].x=0, p[4].y=10;   
    p[0]=p[4], p[5]=p[1];   
}  

int dcmp(double x)
{    
if (x < -eps)   
return -1;  
else   
return (x > eps);      
}
point intersect(const point &p1, const point &p2, double a, double b, double c) 
point g; 
double u = fabs(a * p1. x + b * p1. y + c);    
double v = fabs(a * p2. x + b * p2. y + c);    
g.x=(p1.x*v + p2.x*u)/(u+v),g.y=(p1.y*v+p2.y*u)/(u+v);    
return g;
}      
void cut(double a, double b, double c)
{    
int s = 0,i;    
for ( i = 1; i <= sz; i++) 
{     
if (dcmp((a * p[i]. x + b * p[i]. y + c)*flag) >=0)    
q[++s] = p[i];  
else  
{      
if (dcmp((a * p[i - 1]. x + b * p[i - 1]. y + c)*flag) > 0)       
q[++s] = intersect(p[i-1], p[i], a, b, c);      
if (dcmp((a * p[i + 1]. x + b * p[i + 1]. y + c)*flag) > 0)       
q[++s] = intersect(p[i], p[i+1], a, b, c);     
}    
for ( i = 1; i <= s; i++)  
p[i] = q[i];     
p[s+1] = p[1]; 
p[0] = p[s];    
sz = s;  
}
void solve(point p0,point t1,point t2)
{
double a,b,c;
a=t2.y-t1.y;
b=t1.x-t2.x;
c=t2.x*t1.y-t2.y*t1.x;
flag=a*p0.x+b*p0.y+c;
cut(a,b,c);
}
int main()
{
int i,c=1;
char s[20];
double area;
point p1,p2,t1,t2;
p1.x=0;p1.y=0;
init();
while(scanf("%lf%lf%s",&p2.x,&p2.y,s)!=EOF)
{
       t1.x=(p1.x+p2.x)/2;
       t1.y=(p1.y+p2.y)/2;
       t2.x=t1.x+p1.y-p2.y;
       t2.y=t1.y+p2.x-p1.x;
       area=0;
       if(strcmp("Same",s)==0||!c)
       {
        printf("0.00\n");
c=0;
        continue;
  }
       if(strcmp("Colder",s)==0)
solve(p1,t1,t2);
  else if(strcmp("Hotter",s)==0)
solve(p2,t1,t2);
  for(i=1;i<=sz;i++)
area+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;
      printf("%.2f\n",fabs(area)/2);
      if(fabs(area)/2<eps)
        c=0;
      p1=p2;
}
return 0;
}
       

  评论这张
 
阅读(507)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018