- 浏览: 37592 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Telescope
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 1178
Accepted: 308
Description
Updog is watching a plane object with a telescope. The field of vision in the telescope can be described as a circle. The center is at the origin and the radius is R. The object can be seen as a simple polygon of N vertexes. Updog wants to know the area of the part of the object that can be seen in the telescope.
Input
The input will contain several test cases. For each case:
The first line contains only one real number R.
The second line contains an integer N. The following N lines contain two real numbers xi and yi each, which describe the coordinates of a vertex. Two vertexes in adjacent lines are also adjacent on the polygon.
Constraints: 3 ≤ N ≤50, 0.1 ≤ R ≤1000, -1000 ≤ xi, yi ≤ 1000
Output
For each test case, output one real number on a separate line, which is the area of the part that can be seen. The result should be rounded to two decimal places.
Sample Input
10 3 0 20 10 0 -10 0
Sample Output
144.35
Source
8994621 | GZHU1006100106 | 3675 | Accepted | 224K | 0MS | C++ | 2887B | 2011-07-25 15:52:39 |
#include <iostream> #include <cmath> using namespace std; #define MAXI 0x400 #define sq(x) ((x) * (x)) #define sng(x) (x == 0.0? 0.0: (x > 0? 1.0: -1.0)) #define fmax(x, y) (x > y? x: y) #define fmin(x, y) (x < y? x: y) struct pt { double x, y; pt(double a = 0, double b = 0) { x = a; y = b; } double len() { return sqrt(sq(x) + sq(y)); } double operator * (pt o) { return x * o.y - o.x * y; } double operator % (pt o) { return x * o.x + y * o.y; } } ps[MAXI]; struct sg { pt a, b; double A, B, C; sg(pt x, pt y) { a = x; b = y; A = a.y - b.y; B = b.x - a.x; C = -(a.y * B + a.x * A); } bool ons(pt o) { if (fmin(a.x, b.x) <= o.x && o.x <= fmax(a.x, b.x)) if (fmin(a.y, b.y) <= o.y && o.y <= fmax(a.y, b.y)) return 1; return 0; } double len() { return sqrt(sq(a.x - b.x) + sq(a.y - b.y)); } double ang() { return acos((a % b) / (a.len() * b.len())); } pt inr(sg o) { double d = (A * o.B - o.A * B); double x = B * o.C - o.B * C; double y = A * o.C - o.A * C; return pt(x / d, -y / d); } }; double r; int n; double TGL(pt a, pt b) //Triangulate { #if 0 printf("a = [%.2lf, %.2lf], b = [%.2lf, %.2lf]\n", a.x, a.y, b.x, b.y); putchar('\n'); #endif double sn = sng(a * b); if (a.len() < b.len()) swap(a ,b); pt lp(a.x - b.x, a.y - b.y), np(-lp.y, lp.x), cp; sg l(a, b), nl(pt(0, 0), np); pt tp = l.inr(nl); double tsu = 0; double oa = a.len(); double ob = b.len(); double ol = tp.len();; double ang, d; if (oa == 0.0 || oa == 0.0 || ol == 0.0) return 0.0; if (oa <= r && ob <= r) { tsu += fabs(a * b / 2.0); #if 0 printf("stu 1"); putchar('\n'); #endif } else if (oa > r && ob <= r) { d = sqrt(sq(r) - sq(tp.len())) / l.len(); tp = pt(tp.x + lp.x * d, tp.y + lp.y * d); ang = sg(a, tp).ang(); tsu += ang * sq(r) / 2.0; tsu += fabs(tp * b/ 2.0); #if 0 printf("stu 2"); printf("tp = [%.2lf, %.2lf]\n", tp.x, tp.y); printf("part1 : %.2lf part2 %.2lf\n", ang * sq(r) / 2.0, fabs(tp * b/ 2.0)); putchar('\n'); #endif } else { ang = acos(ol / r); tsu += l.ang() * sq(r) / 2.0; if (oa > r && ob > r && ol < r && l.ons(tp)) tsu += ol * r * sin(ang) - ang * sq(r); #if 0 printf("stu 3\n"); printf("%.2lf\n", acos(ol / r)); printf("part1 : %.2lf part2 %.2lf\n", l.ang() * sq(r) / 2.0, ol * r * sin(ang) - ang * sq(r)); putchar('\n'); #endif } #if 0 printf("tsu = %.2lf\n\n", tsu * sn); #endif return tsu * sn; } int main() { int i; double tsu; while (scanf("%lf", &r) != EOF) { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%lf%lf", &ps[i].x, &ps[i].y); tsu = 0.0; for (i = 0; i < n; i++) tsu += TGL(ps[i], ps[(i + 1) % n]); printf("%.2lf\n", fabs(tsu)); } return 0; }
发表评论
-
HDU 1058 Humble Numbers
2011-08-02 15:55 1225Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 818find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 1015Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 764box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 849Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 1027Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1208二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 1028Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 904Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 797Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1063分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1285Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1124Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 685Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 605find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 704N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 797Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 676开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1174 爆头 .
2011-07-31 20:16 613爆头 Time Limit: 2000/1000 M ... -
HDU 1316 How Many Fibs? .
2011-07-31 20:15 978How Many Fibs? Time Limit: 200 ...
相关推荐
此数据集用于NLP中分词训练使用,文档中的文字已经人工切分好词组,总共有65536个中国汉字组合而成
在编程竞赛的世界里,北京大学(PKU)的ACM团队以其高质量的题目和独特的解题思路闻名。"PKU-ACM.rar"这个压缩包包含了北大ACM题目的一些核心知识点,旨在帮助参赛者理解和掌握算法竞赛中的生命周期题目解法。本文将...
EMF.Eclipse Modeling Framework.2nd.PKU.SEI.SA.part2
EMF.Eclipse Modeling Framework.2nd.PKU.SEI.SA.part1
本软件是一个穿梭到北大未名(bbs.pku.edu.cn)的穿梭服务器程序。北大校内用安装本软件后,别人就可以通过telenet您自己的机器而登陆到北大未名bbs了. 本软件占用内存极少,通常是1到2M; 占用CPU时间约为0.01%。 A....
ACM.PKU解题报告.part2
"p_acm"、"pku_acm"以及"pu_acm.pku_pku"等标签可能是用于分类或标识这些代码属于北京大学(Peking University, PKU)的ACM训练题目。"acm"一词重复出现,进一步强调了这是关于ACM编程竞赛的内容。 描述中提到"acmer...
深度优先遍历 搜索算法 ACM PKU 1011 S.doc
标题中的“PKU_2411.rar_2411 p_pku 2411”似乎是指北京大学(Peking University, 简称PKU)的一个课程或比赛编号2411,其中包含了“rar”后缀的压缩文件。这个压缩包可能包含了该课程或活动的相关资料,如作业、项目...
北京大学(PKU)在计算机科学领域享有盛誉,其在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest, ICPC)方面的成就更是备受瞩目。"PKU+ACM.rar"这个压缩包显然包含了与北大ACM竞赛相关...
- 实验班讲义和作业发布(包括实习作业):`http://db.pku.edu.cn/mzhang/ds/honor/` - 实习课讲义和作业发布:`http://db.pku.edu.cn/mzhang/DS/shixi/` 这些资源提供了学习者获取课程材料及提交作业的方式,有...
这份"Pku题目分类.doc"文件提供了北京大学(Peking University, PKU)编程竞赛中的一些题目分类,涵盖了许多不同的算法和问题类型。以下是对这些标签和题目类型的详细解释: 1. **送分题**:这类题目通常相对简单,...
这个名为"PKU的csapp.zip"的压缩包文件显然包含了与北京大学(Peking University,简称PKU)相关的CSAPP课程相关的学习资源,特别是针对期末考试的复习材料。 首先,我们可以从"体系结构"这一标签中挖掘出以下几个...
《北京大学PKU ACM竞赛题目解析》 北京大学(Peking University, 简称PKU)作为中国顶级学府,其在计算机科学领域的教育和竞赛有着深厚的底蕴。ACM(International Collegiate Programming Contest,国际大学生程序...
标题中的"ACM-PKU-DP.zip_源码"表明这是一个与算法竞赛相关的压缩包,特别是北京大学(PKU)的动态规划(DP)问题的源代码集合。动态规划是一种解决复杂问题的有效方法,通常用于优化决策过程,通过将大问题分解为多...
苯丙酮尿症(PKU)是一种罕见的遗传性代谢疾病,主要影响氨基酸代谢路径,导致苯丙氨酸无法正常转化为酪氨酸,进而积累过多的苯丙酮酸在体内,对神经系统造成损害,尤其是对儿童的智力发展有严重影响。新生儿疾病...
ACM PKU 解题报告 锻炼算法的好东西! 前面的很多题的解题报告。
- [题目2](http://acm.pku.edu.cn/JudgeOnline/problem?id=2288) —— 经典的旅行商问题(TSP),需要考虑如何找到一个最小化的环路。 - [题目3](http://acm.pku.edu.cn/JudgeOnline/problem?id=2411) —— 状态压缩...
描述中的"http://acm.pku.edu.cn/JudgeOnline/problem?id=3728"是一个链接,指向PKU的在线评判系统,这个系统用于提交和测试参赛者的程序代码。 标签 "pku_3621_pasc pku_3728" 暗示了可能存在两个不同的问题或挑战...