http://acm.nyist.net/JudgeOnline/problem.php?pid=3

2024-01-10 07:32

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=3,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一道计算几何求多边形重心问题,

题意:已知一多边形没有边相交,质量分布均匀。顺序给出多边形的顶点坐标,求其重心。

1,质量集中在顶点上。n个顶点坐标为(xi,yi),质量为mi,则重心
  X = ∑( xi×mi ) / ∑mi
  Y = ∑( yi×mi ) / ∑mi
  特殊地,若每个点的质量相同,则
  X = ∑xi / n
  Y = ∑yi / n

2,质量分布均匀。这个题就是这一类型,算法和上面的不同。
  特殊地,质量均匀的三角形重心:
  X = ( x0 + x1 + x2 ) / 3
  Y = ( y0 + y1 + y2 ) / 3

这一题这两种方法都用到了,首先是把该多边形划分成多个三角形,并求出每个三角形的面积和重心,然后以每个三角形的重心为顶点,构造出一个新的多边形,而该多边形和原多边形的重心相同,只是该多边形的质量都集中在顶点上了,因此可以用第一种方法来求,又因为质量和面积成正比,因此可以转化为求三角形面积,至于如何求三角形面积可以用叉积,注意当三角形在多边形外边时为负,这里判断三角形面积为正还是负的方法还可以用右手螺旋定则,如果是顺时针这位负,逆时针为正

AC代码:

#include<cstdio>
#include<cmath>
#include<string>
#define exp 1e-7
using namespace std;
typedef struct str
{double x;double y;str():x(0.0),y(0.0){}
}point;
point s[10005];
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=0;i<n;++i)scanf("%lf%lf",&s[i].x,&s[i].y);double sum=0.0;point cur;for(int i=1;i<=n;++i ){double temp=(s[i%n].x*s[i-1].y-s[i-1].x*s[i%n].y)/2;//以原点为基准点sum+=temp;cur.x+=temp*(s[i%n].x+s[i-1].x)/3.0;cur.y+=temp*(s[i%n].y+s[i-1].y)/3.0;}if(fabs(sum-0.0)<exp) printf("0.000 0.000\n");else  printf("%.3lf %.3lf\n",sum,(cur.x+cur.y)/sum);}return 0;
}


这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=3的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/590030

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时,发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null,再判断Count。 看了一下Count的源码如下: 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get

2、PF-Net点云补全

2、PF-Net 点云补全 PF-Net论文链接:PF-Net PF-Net (Point Fractal Network for 3D Point Cloud Completion)是一种专门为三维点云补全设计的深度学习模型。点云补全实际上和图片补全是一个逻辑,都是采用GAN模型的思想来进行补全,在图片补全中,将部分像素点删除并且标记,然后卷积特征提取预测、判别器判别,来训练模型,生成的像

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

【Linux】应用层http协议

一、HTTP协议 1.1 简要介绍一下HTTP        我们在网络的应用层中可以自己定义协议,但是,已经有大佬定义了一些现成的,非常好用的应用层协议,供我们直接使用,HTTP(超文本传输协议)就是其中之一。        在互联网世界中,HTTP(超文本传输协议)是一个至关重要的协议,他定义了客户端(如浏览器)与服务器之间如何进行通信,以交换或者传输超文本(比如HTML文档)。

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

Anaconda 中遇到CondaHTTPError: HTTP 404 NOT FOUND for url的问题及解决办法

最近在跑一个开源项目遇到了以下问题,查了很多资料都大(抄)同(来)小(抄)异(去)的,解决不了根本问题,费了很大的劲终于得以解决,记录如下: 1、问题及过程: (myenv) D:\Workspace\python\XXXXX>conda install python=3.6.13 Solving environment: done.....Proceed ([y]/n)? yDownloa