- 题目描述: http://poj.org/problem?id=1981
- 题目大意: 给定n 个点的坐标, 求单位圆最多可以覆盖(包括在圆上)多少个点.
- 题目分析: 假设某单位圆能覆盖最多点, 可以右移该单位圆, 使得恰有两个点(或更多)在圆上. 所以思路是,枚举以任意两点,以及半径为1 所确定的圆(有两个,总是选圆心在右, 或在左的那个圆)即可.
#include <iostream> #include <cmath> using namespace std; #define eps 1e-6 struct Point { double x, y; Point() { x = y = 0.00; } }; //返回两点间距 double dist(Point p1, Point p2) { return sqrt( (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) ); } //判断点在圆内(包括圆上) bool dot_on_in_circle(Point p, Point c, double r) { return (dist(p, c) < r + eps); } //返回p1, p2, 以及半径1, 所确定的圆的圆心(只是其中一个圆心) //保证dist(p1, p2) <= 2.0 Point circle(Point p1, Point p2) { Point mid, ret; mid.x = (p1.x + p2.x) / 2; mid.y = (p1.y + p2.y) / 2; double a = dist(p1, mid); double d = sqrt(1.0 - a * a); if(fabs(p1.x - p2.x) <= eps) { ret.x = mid.x + d; ret.y = mid.y; return ret; } double alpha = atan((p1.y - p2.y) / (p1.x - p2.x)); //double alpha = atan(a / d); ret.x = mid.x + d * sin(alpha); ret.y = mid.y - d * cos(alpha); return ret; } int main() { //freopen("in.txt", "r", stdin); int n, i, j, k, count, max; Point dot[305], cent; while(scanf("%d", &n) != EOF && n) { max = 1; for(i = 0; i < n; i++) scanf("%lf %lf", &dot[i].x, &dot[i].y); for(i = 0; i < n; i++) { for(j = i + 1; j < n; j++) { if(dist(dot[i], dot[j]) > 2.0) continue; count = 0; cent = circle(dot[i], dot[j]); for(k = 0; k < n; k++) { if(dot_on_in_circle(dot[k], cent, 1.0)) count++; } if(count > max) max = count; } } printf("%d\n", max); } return 0; }
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1210题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1026题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 869题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 881题目描述: http://acm.hdu.edu.cn/sh ... -
hdoj 1207 汉诺塔II dp 动态规划
2011-05-15 21:22 1662题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2506 Tiling 递推
2011-05-15 11:18 903题目描述: http://poj.org/problem?i ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1794题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1081题目描述: http://poj.org/problem?i ... -
poj 1012 Joseph
2011-05-10 17:42 1229题目描述:poj.org/problem?id=10 ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1128题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 798题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 713题目描述:http://www.poj.org/proble ... -
poj 1654 Area 多边形面积
2011-04-23 20:10 894题目描述:http://poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 663题目描述:http://poj.org/problem?id= ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 541题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 749题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 834题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1210题目描述:http://poj.org/problem?id= ...
相关推荐
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1011 1012 1013 1014 1015 1017 1018 1019 1028 1032 1035 1040 1042 1045 1046 1047 1050 1056 1061 1062 1063 1065 1067 1068 1080 1083 1088 1089 1091 1094 ...
acm pku poj 1000 1001 1002 1003 1201
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
用Java代码实现POJ(PKU)上题2494!
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 2403 Hay Points.md
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
acm 1001 到1009代码,已通过验证
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there...