Posted on 2010-08-22 12:53
lzh525 阅读(421)
评论(0) 编辑 收藏 引用 所属分类:
ＡＣＭ解题报告
将问题转化为点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 }