做的正儿八经的计算几何题不多，慢慢来吧。
题目描述： http://codeforces.com/contest/975/problem/E
大意就是说给你一个凸多边形，一开始1，2两点有钉子固定在墙上，有两种操作，一种是拔掉某个已有钉子的点上的钉子，之后等待该多边形在重力作用下稳定之后固定在该操作中告诉你的另一个点上；另一种是问某个点，输出该点的坐标。
这道题只有从角度相对重心的角度和距离不变，从这儿入手，因此需要计算出一开始多边形的重心并在之后每一个拔钉插钉操作后进行更新，还有每个点与重心的角度和距离，之后可以进行计算坐标；可将多边形切割为多个三角形，因为每个三角形重心计算公式为三点坐标的平均值，之后代入重心计算公式即可；注意为了精度控制，需要将多边形移至原点进行计算，输出时再加上差值；
重心计算公式：X = ∑xi*mi / M；Y = ∑yi*mi / M;
将每个三角形面积和已知的重心坐标代入，计算即可；
代码：
1 #include "iostream" 2 #include "math.h" 3 #include "stdio.h" 4 #include "algorithm" 5 #include "stdlib.h" 6 #include "map" 7 using namespace std; 8 typedef long double ld; 9 typedef pair<ld, ld> point; 10 const ld PI = acosl(-1); 11 point po[10005]; 12 ld angle[10005], dist[10005]; 13 int n, q; 14 point getCenterPos(){ //获取重心 15 ld area, tmp, rx, ry; 16 area = tmp = rx = ry = 0.0; 17 for(int i = 0; i < n; i++){ 18 tmp = po[i].first*po[(i+1)%n].second - po[i].second*po[(i+1)%n].first; //分割的三角形面积 19 area += tmp; 20 rx += tmp*(po[i].first + po[(i+1)%n].first); 21 ry += tmp*(po[i].second + po[(i+1)%n].second); 22 } 23 return point(rx/(3*area), ry/(3*area)); 24 } 25 ld getdist(point a, point b){ //点与重心距离 26 return sqrtl((a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second)); 27 } 28 point getPos(int pos, point center, ld addAng){ //获取点坐标 29 ld x, y; 30 x = center.first + dist[pos]*cosl(angle[pos] + addAng); ///重心坐标变化之后需要将记录的角度变化量加上 31 y = center.second + dist[pos]*sinl(angle[pos] + addAng); 32 return point(x, y); 33 } 34 int main(){ 35 //freopen("test.txt", "r", stdin);//////////////// 36 int i, t, op, a, b, one, two; 37 ld initX, initY, changeAng; 38 point centerPos, top; 39 while(cin>>n>>q){ 40 for(i = 0; i < n; i++) cin>>po[i].first>>po[i].second; 41 initX = po[0].first, initY = po[0].second; 42 for(i = 0; i < n; i++) po[i].first -= initX, po[i].second -= initY; //以第一个点为原点 43 one = 0, two = 1; //初始钉子位置 44 centerPos = getCenterPos(); //初始重心位置 45 changeAng = 0.0; 46 for(i = 0; i < n; i++){ 47 dist[i] = getdist(po[i], centerPos); 48 angle[i] = atan2l(po[i].second - centerPos.second, po[i].first - centerPos.first); //计算角度 49 } 50 while(q--){ 51 cin>>op; 52 if(op == 1){ 53 cin>>a>>b; 54 a--, b--; 55 if(a == one){ 56 one = b; 57 top = getPos(two, centerPos, changeAng); //获取本次旋转点的当前坐标 58 t = two; 59 } 60 else{ 61 two = b; 62 top = getPos(one, centerPos, changeAng); 63 t = one; 64 } 65 //这里计算角度时和之前计算角度值的点顺序相反，画画角度就知道，这样的方式为角与补角的关系（atan2()参数及返回值） 66 changeAng += -PI/2.0 - atan2l(centerPos.second - top.second, centerPos.first - top.first); //记录变化角 67 while(changeAng > 2*PI) changeAng -= 2*PI; 68 while(changeAng < 0) changeAng += 2*PI; 69 centerPos.first = top.first; //更新重心坐标 70 centerPos.second = top.second - dist[t]; 71 } 72 else{ 73 cin>>a; 74 top = getPos(a-1, centerPos, changeAng); 75 printf("%.10lf %.10lfn", (double)(top.first+initX), (double)(top.second+initY)); 76 } 77 } 78 } 79 return 0; 80 }
==！
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
