UVAOJ 10112 基础题 Myacm三角形 几何计算
发布日期:2022-03-30 20:19:25 浏览次数:35 分类:博客文章

本文共 3519 字,大约阅读时间需要 11 分钟。

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1053

Problem B: Myacm Triangles

Source file: triangle.{ccppjavapas}
Input file: triangle.in
Output file: triangle.out

There has been considerable archeological work on the ancient Myacm culture. Many artifacts have been found in what have been called power fields: a fairly small area, less than 100 meters square where there are from four to fifteen tall monuments with crystals on top. Such an area is mapped out above. Most of the artifacts discovered have come from inside a triangular area between just three of the monuments, now called the power triangle. After considerable analysis archeologists agree how this triangle is selected from all the triangles with three monuments as vertices: it is the triangle with the largest possible area that does not contain any other monuments inside the triangle or on an edge of the triangle. Each field contains only one such triangle.

Archeological teams are continuing to find more power fields. They would like to automate the task of locating the power triangles in power fields. Write a program that takes the positions of the monuments in any number of power fields as input and determines the power triangle for each power field.

A useful formula: the area of a triangle with vertices (x1y1), (x2y2), and (x3y3) is the absolute value of

 

0.5 × [(
y
3 
- 
y
1)(
x
2 
- 
x
1
- (
y
2 
- 
y
1)(
x
3 
- 
x
1)].

 

For each power field there are several lines of data. The first line is the number of monuments: at least 4, and at most 15. For each monument there is a data line that starts with a one character label for the monument and is followed by the coordinates of the monument, which are nonnegative integers less than 100. The first label is A, and the next is B, and so on.

There is at least one such power field described. The end of input is indicated by a 0 for the number of monuments. The first sample data below corresponds to the diagram in the problem.

For each power field there is one line of output. It contains the three labels of the vertices of the power triangle, listed in increasing alphabetical order, with no spaces.

Example input:

6A 1 0B 4 0C 0 3D 1 3E 4 4F 0 64A 0 0B 1 0C 99 0D 99 990

Example output:

BEFBCD
1 /************************************************************************* 2     > File Name: 12345.cpp 3     > Author: acmicpcstar 4     > Mail: acmicpcstar@gmail.com 5     > Created Time: 2014年04月24日 星期四 11时46分18秒 6  ************************************************************************/ 7  8 #include
9 #include
10 #include
11 #include
12 #include
13 using namespace std;14 const double pi=atan(1.0)*4.0;15 struct point16 {int num;int x,y;}17 pp[16];18 struct tri19 {int p1,p2,p3;20 int area;21 }22 tt[3000];23 ;24 bool cmp (tri a,tri b)25 {26 return a.area>b.area;27 }28 int mianji(point p1,point p2,point p3)29 {30 return abs((p3.y - p1.y)*(p2.x - p1.x) - (p2.y -p1.y)*(p3.x - p1.x));31 }32 33 int main()34 {int T;35 36 while(cin>>T&&T!=0)37 {int tot=0;38 for(int i=0;i
>ch>>pp[i].x>>pp[i].y;41 pp[i].num=i;42 }43 44 for(int i=0;i
0)53 {54 tt[tot].p1=i;55 tt[tot].p2=j;56 tt[tot].p3=k;57 tt[tot].area=sum2009;58 tot++;59 }60 61 }62 63 }64 }65 sort(tt,tt+tot,cmp);66 int mark;67 for(int i=0;i

面积是叉积乘2为了避免浮点数的计算直接用叉积。。。求2倍面积。。。如果点在三角形里面那么。点。。。和另2个点组成的3个3角形的和总的3角形1样就可以了。。。。我看网上进一步只要另1个点。。。到3顶点的距离相等也是可以用这个来算的。

转载地址:https://www.cnblogs.com/acmicpcstar/p/3687108.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:UVAOJ 10387 基础题 台球 几何计算题
下一篇:UVAOJ 575 基础题 斜二进制数 数论

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月12日 17时53分54秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

webpack卸载_webpack的安装 2019-04-21
mysql主库线程_MySQL 主从扩展--主库的线程状态 2019-04-21
phpmyadmin管理mysql_LAMP实验二:使用phpMyAdmin管理MySQL 2019-04-21
mysql一秒最多写多少次_Mysql的两种“超过多少次”写法(力扣596) 2019-04-21
mysql el函数_MySQL中的常用函数 2019-04-21
mysql 备份 晓燕_mysql字符串函数 2019-04-21
mysql返回第n个值_获取mysql一组数据中的第N大的值 2019-04-21
java读文件几种方式_JAVA读取文件的几种方式 2019-04-21
java arraylist常用方法_C#中数组、ArrayList、List、Dictionary的用法与区别浅析(存取数据)... 2019-04-21
如何实现java文档注释_JavaDoc注释与帮助说明文档 2019-04-21
Java一亿电话号码去重_20 亿个数字在 4G 内存中如何去重排序:快来试一试 BitMap... 2019-04-21
java判断ipv6地址类型_IPv6地址类型与格式 2019-04-21
linux java jdk_linux安装JDK 2019-04-21
java的showcase_java – 如何在Eclipse中导入ShowcaseView? 2019-04-21
JAVA中math的作用_Java中Random 和 Math 的概述及使用(二十六) 2019-04-21
mysql排序rank_MySQL_实现组内排序-Oracle中的rank()函数的功能 2019-04-21
vim自定义html,html - 寻找一种使用VIM在HTML中直接生成漂亮代码段的方法 - 堆栈内存溢出... 2019-04-21
python时间序列因果检验_用python做时间序列预测八:Granger causality test(格兰杰因果检验)... 2019-04-21
python numpy 函数详解_python使用numpy中的size()函数实例用法详解 2019-04-21
java spring上传文件_Java Spring文件上传,Java文件上传,Java通用文件上传 2019-04-21