关键词:
1 /* 2 Name:nyoj-3-多边形重心问题 3 Copyright: 4 Author: 5 Date: 2018/4/26 21:25:41 6 Description: 7 ACM国际大学生程序设计竞赛 算法与实现的模板 8 */ 9 #include <iostream> 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 using namespace std; 14 const double eps = 1e-8; 15 int cmp(double x) 16 if (fabs(x) < eps) return 0; 17 if (x >0 )return 1; 18 return -1; 19 20 //point 21 struct point 22 double x, y; 23 point () 24 point (double a, double b):x(a), y(b) 25 void input() 26 scanf("%lf %lf", &x, &y); 27 28 friend point operator - (const point &a, const point &b) 29 return point(a.x-b.x, a.y-b.y); 30 31 friend point operator + (const point &a, const point &b) 32 return point(a.x+b.x, a.y+b.y); 33 34 friend point operator * (const double &a, const point &b) 35 return point (a * b.x, a*b.y); 36 37 friend point operator / (const point &a, const double &b) 38 return point (a.x / b, a.y /b); 39 40 friend bool operator == (const point &a, const point &b) 41 return (cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0); 42 43 ; 44 double det(const point &a, const point &b) 45 return a.x * b.y - a.y * b.x; 46 47 //polygon 48 const int MAXN = 10009; 49 struct polygon 50 int n; 51 point a[MAXN]; 52 polygon() 53 54 double area() 55 double sum = 0; 56 a[n] = a[0]; 57 for (int i=0; i<n; i++) sum+=det(a[i+1], a[i]); 58 return sum/2; 59 60 point MassCenter() 61 point ans = point(0, 0); 62 if (cmp(area()) == 0) return ans; 63 a[n] = a[0]; 64 for (int i=0; i<n; i++) ans = ans + det(a[i+1], a[i]) * (a[i] + a[i+1]) ; 65 return ans / area()/6; 66 67 ; 68 int main() 69 70 int n; 71 cin>>n; 72 while (n--) 73 int m; 74 cin>>m; 75 polygon pgon; 76 pgon.n = m; 77 for (int i=0; i<m; i++) 78 cin>>pgon.a[i].x>>pgon.a[i].y; 79 80 point ans = pgon.MassCenter(); 81 printf("%.3f %.3f\n", pgon.area(), ans.x+ans.y); 82 83 return 0; 84
nyoj3多边形重心问题(代码片段)
多边形重心问题时间限制:3000ms | 内存限制:65535KB难度:5 描述 在某个多边形上,取n个点,这n个点顺序给出,按照给出顺序将相邻的点用直线连接,(第一个和最后一个连接),所有线段不和其他线段相交,但... 查看详情
poj3855计算几何·多边形重心(代码片段)
思路:多边形面积->任选一个点,把多边形拆成三角,叉积一下三角形重心->(x1+x2+x3)/3,(y1+y2+y3)/3多边形重心公式题目中有,套一下就好了 计算多边形重心方法:(1)划分多边形为三角形:以多边形的一个顶点V为源点(V... 查看详情
多边形重心,面积(代码片段)
多边形面积改革春风吹满地#include<bits/stdc++.h>usingnamespacestd;structpointdoublex,y;node[10001];doublecosr(pointa,pointb,pointc)return(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);intmain()intn;while(cin&g 查看详情
hdu1115多边形求重心模板
1.质量集中在顶点上。n个顶点坐标为(xi,yi),质量为mi,则重心(∑(xi×mi)/∑mi,∑(yi×mi)/∑mi)2.质量分布均匀。这个题就是这一类型,算法和上面的不同。特殊地,质量均匀的三角形重心:((x0+x1+x2)/3,Y=(y0+y1+y2)/3)以(0,0)为顶点三角剖... 查看详情
计算几何
...在直线/线段上5.判断点和三角形位置关系6.判断点是否在多边形中(线段,矩形,圆等等)7.判断线段是否相交8.求多边形面积9.求凸多边形重心 查看详情
79-多边形的面积-计算几何(代码片段)
...php?pid=3 多边形重心问题时间限制:3000 ms | 内存限制:65535 KB难度:5 描述在某个多边形上,取n个点,这n个点顺序给出,按照给出顺序将相邻的点用直线连接,... 查看详情
hdu1115(计算多边形几何重心)
...wproblem.php?pid=1115 题意:给出一些点,求这些点围成的多边形的重心; 思路:方法1:直接分别求所有点的x坐标的平均值和y坐标的平均值,即答案;不过这个方法的计算精度不是很高,要求高精度时用另一个方法; 方... 查看详情
hdu1115liftingthestone(几何,求多边形重心模板题)
转载请注明出处:http://blog.csdn.net/u012860063题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1115LiftingtheStoneProblemDescriptionTherearemanysecretopeningsinthefloorwhicharecoveredbyabigheavystone.Whenthest 查看详情
多边形的面积怎么求?
利用边心距计算规则多边形面积1规则多边形面积的一个计算公式是:面积=1/2x周长x边心距。2获得多边形的边心距。如果题目让你用的是边心距方法,一般来说题里都会给出边心距的大小。比如你要计算一个正六边形的面积,该... 查看详情
计算几何常用的函数/方法(代码片段)
(一)求多边形的面积(用叉积计算)代码如下:1//叉积,可以用来判断方向和求面积23doublecross(Pointa,Pointb,Pointc)45return(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);678910111213//求多边形的面积1415doubleS(Pointp[],intn)1617doubleans=0;1819p[n]=p[0];2021for(inti=1;i&l... 查看详情
poj1385liftingthestone多边形重心
POJ1385给定n个顶点顺序连成多边形求重心n<=1e+6比较裸的重心问题没有特别数据由于答案保留两位小数四舍五入需要+0.0005消除误差#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include& 查看详情
cows计算几何求凸包求多边形面积(代码片段)
题目链接:https://cn.vjudge.net/problem/POJ-3348题意啊模版题啊求凸包的面积,除50即可思路求凸包的面积,除50即可提交过程AC代码#include<cmath>#include<cstdio>#include<vector>#include<algorithm>usingnamespacestd;constdou 查看详情
hdu2036求多边形面积(凸凹多边形)(代码片段)
...块。这块田位于浙江省温州市苍南县灵溪镇林家铺子村,多边形形状的一块地,原本是li 查看详情
java计算四边形中心点和两条线段交点算法(代码片段)
...四边形两条对角线的交点即为中心点。先来复习下三角形面积公式:已知三角形三点a(x,y)b(x,y)c(x,y),三角形面积为: doubletriArea=((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))/2; 因为两向量叉乘==两向量构成的平行四边形(以两向量为邻边)... 查看详情
c语言怎么输入半径求圆面积和周长?
...图形。对称轴是直径所在的直线。同时,圆又是“正无限多边形”,而“无限”只是一个概念。圆可以看成由无数个无限小的点组成的正多边形,当多边形的边数越多时,其形状、周长、面积就都越接近于圆。圆的相关性质:1... 查看详情
求多边形面积模板***
doublearea(){//top为总点数,即0~top-1,res为点数组doublesum;sum=res[0].y*(res[top-1].x-res[1].x);for(inti=1;i<top;i++)sum+=p[res[i]].y*(res[i-1].x-res[(i+1)%top].x);returnsum/2;} 查看详情
正边形求面积(代码片段)
问题F:Icebergs时间限制: 3 Sec 内存限制: 256MB提交 状态题目描述Taniaisamarinebiologist.HergoalistomeasuretheimpactofclimatechangeonthepopulationofMacaronipenguins.Asmostspeciesofpenguins,M 查看详情
hdu-2036求任意多边形面积(代码片段)
改革春风吹满地TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):45028 AcceptedSubmission(s):23074ProblemDescription“改革春风 查看详情