Rolling The Polygon | Kyons'Blog 




 
 
 
 



 
 



Rolling The Polygon

2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest

The 2018/2019 Asia Yinchuan First Round Online Programming

题目大意

一个凸包,凸包上有一个点$G$
在水平面上滚动凸包,问点$G$的滚动轨迹长度是多少.

画一个图
1.png
即求弧长$HH’$
显然~$∠ABN=∠HBH’=∠CBI$
那么,求$∠ABN$就相当于求$\pi-∠ABC$
至于$∠ABC$怎么求,就很显然啦.

点击查看代码
1
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)

typedef struct point vec;
struct point { //点的基本数据结构
double x, y;
double d;
point(double _x = 0, double _y = 0)
: x(_x)
, y(_y)
{
}
point operator*(const point& i_T) const
{
return point(x * i_T.x, y * i_T.y);
}
point operator*(double u) const
{
return point(x * u, y * u);
}
bool operator==(const point& i_T) const
{
return x == i_T.x && y == i_T.y;
}
point operator/(double u) const
{
return point(x / u, y / u);
}
point operator+(const point& i_T)
{
return point(x + i_T.x, y + i_T.y);
}
point operator-(const point& i_T)
{
return point(x - i_T.x, y - i_T.y);
}
friend bool operator<(point a, point b)
{
return a.y == b.y ? a.x < b.x : a.y < b.y;
}
friend ostream& operator<<(ostream& out, point& a)
{
//cout << a.x << ' ' << a.y;
printf("%.8f %.8f", a.x, a.y);
return out;
}
friend istream& operator>>(istream& in, point& a)
{
in >> a.x >> a.y;
return in;
}
} p[100];
double changdu(vec a) //向量长度
{
return sqrt(a.x * a.x + a.y * a.y);
}
double dianji(vec A, vec B) //点积
{
return A.x * B.x + A.y * B.y;
}
double jiajiao(vec a, vec b)
{
return pi - acos(dianji(a,b) / (changdu(a) * changdu(b)));
}
int main()
{
point p0;
int n, t, cas = 1;
scanf("%d", &t);
for (int k = 1; k <= t; k++) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
cin >> p[i];
cin >> p0;
for (int i = 1; i <= n; i++)
p[i].d = changdu(p0 - p[i]);
p[0] = p[n], p[n + 1] = p[1];
double ans = 0;
for (int i = 1; i <= n; i++)
ans += p[i].d * jiajiao(p[i - 1]- p[i], p[i + 1]-p[i]);
printf("Case #%d: %.3f\n", k, ans);
}
return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载