文章列表
题目描述: http://poj.org/problem?id=1981
题目大意: 给定n 个点的坐标, 求单位圆最多可以覆盖(包括在圆上)多少个点.
题目分析: 假设某单位圆能覆盖最多点, 可以右移该单位圆, 使得恰有两个点(或更多)在圆上. 所以思路是,枚举以任意两点,以及半径为1 所确定的圆(有两个,总是选圆心在右, 或在左的那个圆)即可.
#include <iostream>
#include <cmath>
using namespace std;
#define eps 1e-6
struct Point {
double x, ...
题目描述: http://poj.org/problem?id=1032
题目大意: 议会有N 个议员, 将他(她)们分成多组. 每次会议每组出一个代表, 且每次会议的代表都不完全相同. 求得一种分组情况, 使得能够开会的次数最多. 说白了就是求N 的一种划分 N = a1 + a2 + ... + a(t-1) + a(t), 使得M = a1 * a2 * ... * a(t - 1) * a(t) 最大.
关于该题的一些规则：
1. 1 < a1 < 4;
假设a1 = 1; 那么一个数乘以a1， 乘积并不变大， 还不如把a1 加给其他元素。
假设a1 > ...
题目描述: http://poj.org/problem?id=1012
题目分析: 该题就是给定多边形n 个顶点, 求重心
//IDE:vc6.0
#include <iostream>
using namespace std;
struct point {
double x, y;
};
double xmult(point p1,point p2,point p0){
return (p1.x - p0.x) * (p2.y - p0.y)
- (p2.x - p0.x) * (p1.y - p0.y);
}
point ...
题目描述: http://poj.org/problem?id=2676
转自: http://zhangjian110518.blog.163.com/blog/static/74991703200933092722785/
题目技巧性不强，DFS过的，用时16MS。不过写的过程中要注意从后面往前搜。
/************************************************************************/
/*思路：
先从后面开始搜，也就是从第八十个开始搜
1、如果一个小的方格内已经包含了非零的数，则继续向下搜
2、如果一个小的 ...
题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=2064(中文)
题目分析:
把n 个盘子从A 间接(不能把盘子直接从A 移到C )移到C 需要以下五步:
1. 把n - 1 个盘子间接从A 移到C, f(n - 1)
2. 把最大的盘子从A 移到B, 1
3. 把n - 1 个盘子间接从C 移到A, f(n - 1)
4. 把最大的盘子从B 移到C 1
5. 把n - 1 个盘子间接从A 移到C, f(n - 1)
易得f(n) = 3 * f(n - 1) + 2, f ...
题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=1207(中文)
题目分析:
以下思路转自:http://yxq0620.blog.163.com/blog/static/4449439220102245168595/
初看很难,理解了会发现真的很简单的...
不明白的建议看一下 http://poj.org/problem?id=1958这题,里面有dp 的思路.
如果不明白就继续看吧.
dp[n]表示 将n个盘子通过4根柱子移动到目的柱子的最小的步数, f( i )表示 把 i个盘子通过 3根柱子移动到目的柱子的最小步数,f( ...
题目描述: http://poj.org/problem?id=2506
题目大意: 使用2 * 1 和 2 * 2 的矩形铺砌2 * n 的矩形, 共有多少种方法?
分析:
假设f ( n ) 为铺砌 2 * ｎ 的矩形的方法种数， 参见下图：
易得 f ( n ) = f ( n - 1 ) + 2 * f ( n - 2 );
f ( 1 ) = 1; f ( 2 ) = 3;
又因为本体要求处理的n 很大, 需要大数处理, 故用Java 的BigInteger 类, 免去用c++ 实现大数加法, 代 ...
题目描述: http://poj.org/problem?id=2420
题目大意: 其实是求n 边形的费马点, 即到n 边形的n 个顶点距离和最小的点,
该题要求计算出最小距离, 并四舍五入.
算法大意: 先拿一个点(该算法用n 个顶点的x, y 坐标和的均值所在的点)去计算距离和
最小值, 然后拿它的四个方向上的点去测试比较哪个点更优, 不断
迭代, 最终得到在精度允许下的费马点.
#include <cstdio>
#include <cmat ...
题目描述: http://poj.org/problem?id=2954
题目大意: 给定顶点都是整数的三角形, 试求出该三角形内部的整点个数(不包括边界).
首先简要描述一下Pick 定理:
给定顶点坐标均是整点（或正方形格点）的简单多边形， Pick 定理说明了其面积S和内部格点数目i、边上格点数目b 的关系：
S = i + b/2 - 1。
(其中i 表示多边形内部的点数,b 表示多边形边界上的点数,S 表示多边形的面积)
Pick 定理在百度百科:http://baike.baidu.com/view/3207200.html
直接浙大 ...
题目描述:poj.org/problem?id=1012
经典Joseph 问题的加强版, 参见注释, 注释很详细.
#include <cstdio>
/*
测试ｍ是否满足要求
k: 有2ｋ个人
ｍ：每数到ｍ就出局 */
bool test(int k, int m) {
int i = 0, len = 2 * k; //len: 当前总人数
while(len > k) {
i = (i + m - 1) % len; //每次出局人是出局前的len 个人中的第i 个, 下标从0 开始
if(i ...
题目描述: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=81
题目大意: n 边形的 n 个顶点按顺序给出, 接下来是m 个测试点, 对于每个测试点判断该点是否在多边形内(包括边界).
直接copy 浙大模板 O(∩_∩)O哈哈~
附上代码
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define offset 10000
#define eps 1e-8
#define zero(x) ( ((x ...
题目描述：http://poj.org/problem?id=1835
该题关键在于方向的处理，代码注释比较详细。
#include <iostream>
using namespace std;
//辅助数组，完成当前坐标修改
int dir[6][3] = {1, 0, 0,
0, 1, 0,
0, 0, 1,
-1, 0, 0,
0, -1, 0,
0, 0, -1};
//方向数组，存储forward, right, up,
//back, left, down ...
1. qsort() (include <stdlib.h>)
qsort() 采用的是快速排序
首先要说的是c 语言中的qsort()，不建议使用qsort()，因为
STL（标准模板库）中的sort() 和 qsort() 的核心都是快速排
序，通常用sort() 就行了。
函数原型：
void qsort ( void * base,
size_t num,
size_t size,
...
题目描述：http://www.poj.org/problem?id=2398
该题算是poj 2318 的加强版，poj 2318 的解题报告见：
http://scott--------.iteye.com/blog/1013250
与2318 相比有一下不同：
1.输入的分割线无序
2.输出要求统计玩具的分布情况，假设m 个分区中都正好有t 个玩具，
要就输出m1: t1, m2: t2,...。按m 大小升序。
#include <cstdio>
#include <algorithm>
using namespace ...
题目描述：http://poj.org/problem?id=1654
题目大意：从平面坐标原点出发，1-9(除了5）表示不同的方向，最终保证回到原点，路径为一多边形，求多边形的面积。
解题思路：因为数据量较大，可以不用保存多边形的每个顶点信息，每次读一个数字（即读一段）就计算该线段与原点组成三角形的有向面积。
1.另外面积area 的保存用int 的话会溢出，所以选用long long(g++） 或__int64(vc6.0)。
2.dir 数组的设计方便求下一个点的坐标，想不到的话就直接switch语句 吧。
#inc ...