- 浏览: 36007 次
文章分类
- 全部博客 (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 1170Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 766find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 995Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 735box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 787Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 968Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1160二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 985Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 864Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 767Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1015分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1230Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1070Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 640Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 571find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 661N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 758Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 643开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1174 爆头 .
2011-07-31 20:16 582爆头 Time Limit: 2000/1000 M ... -
HDU 1316 How Many Fibs? .
2011-07-31 20:15 944How Many Fibs? Time Limit: 200 ...
相关推荐
本软件是一个穿梭到北大未名(bbs.pku.edu.cn)的穿梭服务器程序。北大校内用安装本软件后,别人就可以通过telenet您自己的机器而登陆到北大未名bbs了. 本软件占用内存极少,通常是1到2M; 占用CPU时间约为0.01%。 A....
此数据集用于NLP中分词训练使用,文档中的文字已经人工切分好词组,总共有65536个中国汉字组合而成
EMF.Eclipse Modeling Framework.2nd.PKU.SEI.SA.part1
EMF.Eclipse Modeling Framework.2nd.PKU.SEI.SA.part2
ACM.PKU解题报告.part2
深度优先遍历 搜索算法 ACM PKU 1011 S.doc
acmer pku入门题 初学acm和大一学生适合 附原题
pku题目分类,很详细的....,绝对有用.......
PKU语料库,免费供广大自然语音爱好者你能方便下载人民日报提供的汉语语料库。方便学习。训练集pku_training.utf8,用来训练模型的参数,测试集 pku_test.utf8,用来测验模型的最终准确率。
Pku 2411 Mondriaan 附解题报告
自己做的几道ACM的题,复杂 不是很好,请大家指点指点
ACM PKU 解题报告 锻炼算法的好东西! 前面的很多题的解题报告。
数据结构与算法课件 北大张铭 非常详细非常清晰 学习数据结构和算法的好资料
北大ACM生命周期题目的经典解法。 北大ACM生命周期题目的经典解法。 北大ACM生命周期题目的经典解法。
pascal source code for http://acm.pku.edu.cn/JudgeOnline/problem?id=3728
csapp试题,其中包括一些资料! 对于在学习csapp的学生应付期末考试应该绰绰有余!! 可以参考这个,结合自己的实际情况学习!!! PUK的!!!懂的都懂!!!
实在没什么好东西,就找了以前在北大ACM上做的一些题 比较适合于初学程序设计和算法的同学
在POJ上做的一些动态规划题,自己看吧。
PKU 1000-1050我ac的代码!绝对保证质量!