lzh

刘政
posts - 17, comments - 1, trackbacks - 0, articles - 1

Repackaging(UVa10089)

Posted on 2010-08-22 12:53 lzh525 阅读(421) 评论(0)  编辑 收藏 引用 所属分类: ACM解题报告
将问题转化为点A(0,0)是否在一个凸多边形内的问题........点是否在由其他点围成的多边形里的问题又转化为斜率的问题........

1 #include <cstring>  
 2 #include <iostream>  
 3 #include <string>  
 4 using namespace std;  
 5 typedef long llint;  
 6 llint const maxn = 1001;  
 7 bool repackage(llint pkgs[][3], llint p)  
 8 {  
 9     llint i;
10     for(i=0;i<p;i++)
11     {  
12         pkgs[i][0-= pkgs[i][2]; //转换为二维 
13         pkgs[i][1-= pkgs[i][2];  
14     }  
15     llint x1=pkgs[0][0], y1=pkgs[0][1],x2 = pkgs[0][0], y2=pkgs[0][1];  
16     for (i = 1; i < p; i++)
17     {              
18         llint x = pkgs[i][0], y = pkgs[i][1];  
19         llint a1 = y1 * x, b1 = x1 * y, a2 = y2 * x, b2 = x2 * y;  
20         if (a1 == b1)  
21             if (x1 * x + y1 * y<=0)//如果两点在一条直线上且位于不同项限则(0,0)包含在凸包内
22                 return true;  
23             if (a2 == b2)  
24                 if (x2 * x + y2 * y <= 0)
25                     return true;  
26                 if (a1 < b1)
27                     x1 = x, y1 = y; //保存斜率大的
28                 if (a2 > b2)
29                     x2 = x, y2 = y; //保存斜率小的
30                 if (x1==x2&&y1==y2)//(0,0)点包含在凸包内则“YES”
31                     return true;  
32                 if (y1 * x2 == y2 * x1)  
33                     if (x1 * x2 + y1 * y2 <= 0
34                         return true;  
35                     if (y1 * x2 < y2 * x1)
36                         return true;  
37     }  
38     return false;  
39 }  
40 int main()  
41 {  
42     llint pkgs[maxn][3],p,i;
43     while(cin>>p)        
44     {  
45         if(p==0)
46             break;
47         for (i=0;i<p;i++)  
48             cin>>pkgs[i][0]>>pkgs[i][1]>>pkgs[i][2];  
49         if (repackage(pkgs,p))  
50             cout << "Yes\n";  
51         else  
52             cout << "No\n";  
53     }  
54     return 0;  
55 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理