题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2036
http://acm.hdu.edu.cn/showproblem.php?pid=2108
这两道题目分别是判断一个多边形是否是凸多边形,求一个多边形的面积
题意很简单,题目也不难,算是最基础的计算几何了
参考资料:计算几何基础
参考代码:
hdu2036 by ACShiryu1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
struct ac {
int x ;
int y ;
}po[555555];
int cross(ac a , ac b ,ac c)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
bool convex(int n)
{
for(int i = 0 ; i < n ; i ++)
if(cross(po[i],po[(i+1)%n],po[(i+2)%n])<0)
return false;
return true;
}
int main()
{
int n ;
while (cin >> n , n)
{
for (int i=0;i < n ; i ++ )
cin >> po[i].x >> po[i].y;
if (convex(n))
cout<<"convex"<<endl;
else
cout<<"concave"<<endl;
}
return 0;
}
hdu2108 by ACShiryu1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
struct ac {
int x ;
int y ;
}po[555555];
int cross(ac a , ac b ,ac c)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
bool convex(int n)
{
for(int i = 0 ; i < n ; i ++)
if(cross(po[i],po[(i+1)%n],po[(i+2)%n])<0)
return false;
return true;
}
int main()
{
int n ;
while (cin >> n , n)
{
for (int i=0;i < n ; i ++ )
cin >> po[i].x >> po[i].y;
if (convex(n))
cout<<"convex"<<endl;
else
cout<<"concave"<<endl;
}
return 0;
}