注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 1755 Triathlon 半平面交判断不等式是否有解  

2011-05-08 23:52:06|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=1755

有一个全能运动必有要求运动员完成游泳、骑自行车、跑步,三个项目。冠军为最快完成所有项目的运动员。已知每个运动员的三项速度分别为Vi, Ui, Wi 。裁判能够任意的设置三个项目的路程。问对某个运动员能否设定一个让他必羸的路程设置。

当构造一个a,b,c的距离,使得t = a/u + b/v + c/w 时间最小,就可以了
   那么就可以转化成  (1 / u1 - 1 / u2) * a + (1 / v1 - 1 / v2) * b + (1 / w1 - 1 / w2) * c < 0
   ==> (1 / u1 - 1 / u2) * a / c + (1 / v1 - 1 / v2) * b / c + (1 / w1 - 1 / w2) < 0
   ==> 符合 a * x + b * y + c < 0这样子直接用半平面交求就行了,如果不能构成一个核(点数少于3),就表示无解
   构造不等式 ax + by + c < 0;
   这里具体问题具体分析吧,反正把所有不等式构造成符号同一个方向就行了,然后再把cut函数里面的判断符号也改了

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
const double inf=1e20;
const double eps=1e-10;
const int N=105;int n,sz;
double u[N],v[N],w[N];
struct point
{
  double x,y;
}p[N],q[N];
void init()
{   
 sz = 4;
 p[1].x=p[1].y=0;
 p[2].x=inf, p[2].y=0;   
 p[3].x=p[3].y=inf;   
 p[4].x=0, p[4].y=inf;  
    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) <=0)     
  q[++s] = p[i];    
  else 
  {     
   if (dcmp(a * p[i - 1]. x + b * p[i - 1]. y + c) < 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) < 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;  
}
int solve(int x)
{
 int i;
 for (i=0; i<n;i++) 
 { 
  if (i!=x&&u[x]<=u[i]&&v[x]<=v[i]&&w[x]<=w[i])   
  return 0;
 }
 init();   
 for ( i = 0; i < n; i++) 
 { 
  if (i != x) 
  {        
   double a = 1/u[x] - 1/u[i], b = 1/v[x] - 1/v[i], c = 1/w[x] - 1/w[i];      
   cut(a, b, c);     
   if (sz < 3)   
   return 0;     
  }  
 }    
 return (sz > 2);
}
int main()
{
 int i;
 scanf("%d",&n);
 for(i=0;i<n;i++) 
 scanf("%lf %lf %lf",&u[i],&v[i],&w[i]);
 for(i=0;i<n;i++)
 { 
  if(solve(i))  
  printf("Yes\n"); 
  else  
  printf("No\n");
 }
 system("pause");
 return 0;
}

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

历史上的今天

评论

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

页脚

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