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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

UVA 10089  

2010-03-19 21:37:24|  分类: uva |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定若干三元组(ai1,ai2,ai3)问是否存在bi使得
sigma(bi*ai1)=sigma(bi*ai2)=sigma(bi*ai3)
问题相当于是对于若干向量所组成的多面体,问(1,1,1)是否在其中
可以转化为对于二维向量(ai1-ai2,ai1-ai3)组成的凸包(0,0)是否在其中
#include<cstdio>
long long a[1000][3];
int n;
long long inline aa(int x,int y){
  long long x1=a[x][0]-a[x][1],x2=a[x][0]-a[x][2];
  long long y1=a[y][0]-a[y][1],y2=a[y][0]-a[y][2];
  if(x1*y2>x2*y1)
    return 1;
  if(x1*y2<x2*y1)
    return -1;
  if(x2*y2<0||x1*y1<0||(!x1&&!x2)||(!y1&&!y2))
    return 0;
  return 2;
}
int solve(){
      int i1=0,i2=0;
      for(int i=1;i<n;i++){
        if(aa(0,i)==-1&&aa(i1,i)==-1)
          i1=i;
        if(aa(0,i)==1&&aa(i2,i)==1)
          i2=i;
        if(aa(i1,i2)*aa(i1,0)==-1&&aa(i2,i1)*aa(i2,0)==-1||aa(i1,i2)*aa(i1,0)==0||aa(i2,i1)*aa(i2,0)==0)
          return 1;
      }
      return 0;
}
int main(){
    while(scanf("%d",&n)!=EOF&&n!=0){
      for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
          scanf("%lld",&a[i][j]);
      if(solve())
        printf("Yes\n");
      else printf("No\n");
    }
    return 0;
}

  评论这张
 
阅读(573)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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