英文原题
大意:给定一个三角形(0,0),(m,n),(p,0)求三角形内部的整数格点的数量。
可以用皮克定理求解:给定任意简单多边形,其面积A和内部格点数目i、边上格点数目b的关系:A = i + b/2 - 1。 而线段<(0,0),(n,m)>上的格点数(包含端点)等于n与m的最大公约数+1,从而对多边形而言,边上的格点数总和为边向量的xy分量最大公约数之和(去掉重复计数)。多边形面积为点积和。从而得解。
这里的实现包含了对一般简单多边形的处理。
对这个题而言,还可以参考图形学中的划线算法,对每行得到内部格点的最大最小值,求和得到解。
有意思的是,中文题译与英文原题完全不同,同一个题目名字,内容不同,是较早的电网版本,比这个题要困难一些,摘录如下:
农夫约翰已经决定建造电网。他已经把他的农田围成一些奇怪的形状,现在必须找出安放电源的最佳位置。
对于段电网都必须从电源拉出一条电线。电线可以穿过其他电网或者跨过其他电线。电线能够以任意角度铺设,从电源连接到一段电网的任意一点上(也就是,这段电网的端点上或者在其之间的任意一点上)。这里所说的“一段电网”指的是呈一条线段状的电网,并不是连在一起的几段电网。若几段电网连在一起,那么也要分别给这些电网提供电力。
已知所有的 F(1 <= F <= 150)段电网的位置(电网总是和坐标轴平行,并且端点的坐标总是整数,0 <= X,Y <= 100)。你的程序要计算连接电源和每段电网所需的电线的最小总长度,还有电源的最佳坐标。
电源的最佳坐标可能在农夫约翰的农田中的任何一个位置,并不一是整数。
这是个平面极值问题,如果用解析方法求解,电网的xy坐标将目标区域划分成的网格,网格中每个区域的方程是不同的,需在每个区域内求得极值并最终得到解。不过从编程角度看,用四分法求解就足够了。
大意:给定一个三角形(0,0),(m,n),(p,0)求三角形内部的整数格点的数量。
可以用皮克定理求解:给定任意简单多边形,其面积A和内部格点数目i、边上格点数目b的关系:A = i + b/2 - 1。 而线段<(0,0),(n,m)>上的格点数(包含端点)等于n与m的最大公约数+1,从而对多边形而言,边上的格点数总和为边向量的xy分量最大公约数之和(去掉重复计数)。多边形面积为点积和。从而得解。
这里的实现包含了对一般简单多边形的处理。
对这个题而言,还可以参考图形学中的划线算法,对每行得到内部格点的最大最小值,求和得到解。
有意思的是,中文题译与英文原题完全不同,同一个题目名字,内容不同,是较早的电网版本,比这个题要困难一些,摘录如下:
农夫约翰已经决定建造电网。他已经把他的农田围成一些奇怪的形状,现在必须找出安放电源的最佳位置。
对于段电网都必须从电源拉出一条电线。电线可以穿过其他电网或者跨过其他电线。电线能够以任意角度铺设,从电源连接到一段电网的任意一点上(也就是,这段电网的端点上或者在其之间的任意一点上)。这里所说的“一段电网”指的是呈一条线段状的电网,并不是连在一起的几段电网。若几段电网连在一起,那么也要分别给这些电网提供电力。
已知所有的 F(1 <= F <= 150)段电网的位置(电网总是和坐标轴平行,并且端点的坐标总是整数,0 <= X,Y <= 100)。你的程序要计算连接电源和每段电网所需的电线的最小总长度,还有电源的最佳坐标。
电源的最佳坐标可能在农夫约翰的农田中的任何一个位置,并不一是整数。
这是个平面极值问题,如果用解析方法求解,电网的xy坐标将目标区域划分成的网格,网格中每个区域的方程是不同的,需在每个区域内求得极值并最终得到解。不过从编程角度看,用四分法求解就足够了。
/* ID: blackco3 TASK: fence9 LANG: C++ */ #include <iostream> using namespace std; const int _n_pt_(3) ; struct t_point { int x, y ; t_point(int a=0, int b=0):x(a),y(b){}; } ; inline int iabs(int v) { return v<0 ? -v : v ; } inline int cross(t_point const &a, t_point const &b){ return a.x*b.y - a.y*b.x; } inline int gcd(int a, int b) { while(a && b) a %= b , b = a ? b%a : b ; return a + b ; } inline int grids_on_line(t_point const &a, t_point const &b) { return gcd( iabs(a.x-b.x), iabs(a.y-b.y) ) ; } int poly_area(t_point *poly, int n_size) { int area=0 ; for(int i=0; i<n_size; i++) { area += cross( poly[i], poly[i+1] ); } return iabs(area)/2; } int Pick_grid(t_point *poly, int n_size ) { int sum_bound=0 ; for(int i=0; i<n_size; i++ ) sum_bound += grids_on_line(poly[i], poly[i+1]); return poly_area(poly, n_size) - (sum_bound>>1) + 1; } int main() { freopen("fence9.in", "r", stdin); freopen("fence9.out","w",stdout); t_point poly[_n_pt_+1] ; cin >> poly[1].x >> poly[1].y >> poly[2].x; cout << Pick_grid(poly, _n_pt_) << endl; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 882英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1130英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1843郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1641英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1194英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 964英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1061英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1400英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 771英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 794英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1203英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 912英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1091英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 770英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1228英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1043英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 928英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1304英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 865英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ... -
USACO Training Section 3.2 Stringsobits
2010-01-18 01:04 986英文原题 中文题译 大意:求至多有L个1的第i个N位二进 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco第五章fence3的解题代码,供算法初学者参考
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 Chapter5 5.1 Section 5.1 5.2 Section 5.2 5.3 Section 5.3 5.4 Section 5.4 5.5 Section 5.5
1.歌曲必须按照创作的时间顺序在 CD 盘上出现 2.选中的歌曲数目尽可能地多 3.不仅同光盘上的歌曲写入时间要按顺序,前一张光盘上的歌曲不能比后一张
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
USACO题集及答案