当前位置:首页 >> 数学 >>

ACM计算几何题目总结及分类


COJ http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1011 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1024 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1034 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1035 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1036 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1037 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1038 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1078 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1137 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1172 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1190 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1211 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1230 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1231 http://acm.cug.edu.cn/oj/prepare.do?fun=viewProblem&pid=1249 http://lab.cug.edu.cn:8080/COJ/prepare.do?fun=viewProblem&pid=1257 http://lab.cug.edu.cn:8080/COJ/prepare.do?fun=viewProblem&pid=1260 FOJ Hotter Colder http://acm.fzu.edu.cn/problem.php?pid=1014 求线段的中位线,线段相交求交点,求凸多边形的面积, 无归之室 http://acm.fzu.edu.cn/problem.php?pid=1016 本题精度要求非常高,用三角函数的话,很容易就 wa.. Reflections http://acm.fzu.edu.cn/problem.php?pid=1035 求一条射线遇到圆后的反射光, 即圆和直线求交点,求点关于交点法线的对称点。 Pipe http://acm.fzu.edu.cn/problem.php?pid=1088 求一条光线从管道口进入,最远能达到多远。 判断线段左右位置关系,求线段相交交点。 A Pilot in Danger! http://acm.fzu.edu.cn/problem.php?pid=1120 判断点在区域内 Area in Triangle http://acm.fzu.edu.cn/problem.php?pid=1195 在三角形内的气球膨胀,求膨胀后的面积。 分情况推公式 Triangle http://acm.fzu.edu.cn/problem.php?pid=1302 在给定的 n( 1<=n<=50000)个点中,取 3 个点组成三角形,求面积最大。

显然这 3 个点在凸包上,点集凸包化+凸包上的点 k^2(原来要 k^3 的,利用某些性质剪枝, 降到 k^2). Area http://acm.fzu.edu.cn/problem.php?pid=1329 Pick 定理 Center of Gravity http://acm.fzu.edu.cn/problem.php?pid=1330 已知半径,角度的扇形,求其重心到圆心的距离。 Stone http://acm.fzu.edu.cn/problem.php?pid=1331 求多边形的重心 Surround the Trees http://acm.fzu.edu.cn/problem.php?pid=1333 凸包 Star not a Tree? http://acm.fzu.edu.cn/problem.php?pid=1355 费马点 Coplanar Points http://acm.fzu.edu.cn/problem.php?pid=1393 利用差积判断 4 点共面。 长方形的并的面积 http://acm.fzu.edu.cn/problem.php?pid=1407 离散化 Common Area http://acm.fzu.edu.cn/problem.php?pid=1472 三角形和圆的共同面积。 弹弓 http://acm.fzu.edu.cn/problem.php?pid=1482 n(1<=n<=700)个点中,最多有多少个点在同一条直线上。 牧场 http://acm.fzu.edu.cn/problem.php?pid=1485 n(2<=n<=100)个点中, 取其中部分点组成的一个凸多边形, 求这样的凸多边形的最大顶点数. Oaiei's Trouble http://acm.fzu.edu.cn/problem.php?pid=1510 图形学中的直线剪裁算法, 可以用计算几何中的点和线段的关系, 线段和线段的求交点来求 解。 Defense the country http://acm.fzu.edu.cn/problem.php?pid=1338 Treasure Hunt http://acm.fzu.edu.cn/problem.php?pid=1332 线段相交 Minkowski Sum http://acm.fzu.edu.cn/problem.php?pid=1379 Area Ratio

http://acm.fzu.edu.cn/problem.php?pid=1382 求三角形的内切圆,外接圆 Video Surveillance http://acm.fzu.edu.cn/problem.php?pid=1032 简单题 最大可分离值问题 http://acm.fzu.edu.cn/problem.php?pid=1201 POJ http://acm.pku.edu.cn/JudgeOnline/ 1031 Fence 1039 Pipe 1092 Farmland 1106 Transmitters 1113 Wall 1118 Lining Up 1133 Stars 1151 Atlantis 1225 STRICTLY INSCRIBED SIMILAR TRIANGLES 1259 The Picnic 1263 Reflections 1265 Area 1266 Cover an Arc. 1269 Intersecting Lines 1271 Nice Milk 1279 Art Gallery 1294 Not Too Convex Hull 1319 Pipe Fitters 1347 Triangle 1361 JaWs 1375 Intervals 1379 Run Away 1389 Area of Simple Polygons 1408 Fishnet 1410 Intersection 1418 Viva Confetti 1428 Hermes' Colony 1434 Fill the Cisterns! 1444 Parallelepiped walk 1471 Triangles 1473 There's Treasure Everywhere! 1494 Sunrise 1499 Supercomputer Selection, The Sequel 1500 Polygonal Puzzle

1514 Metal Cutting 1518 Problem Bee 1536 Trains 1556 The Doors 1569 Myacm Triangles 1584 A Round Peg in a Ground Hole 1586 Three Sides Make a Triangle 1605 Horse Shoe Scoring 1610 Quad Trees 1623 Squadtrees 1624 This Takes the Cake 1645 BSP Trees 1654 Area 1660 Princess FroG 1673 EXOCENTER OF A TRIANGLE 1685 Color Tunnels 1687 Buggy Sat 1688 Dolphin Pool 1693 Counting Rectangles 1696 Space Ant 1727 Advanced Causal Measurements (ACM) 1758 Frontier 1765 November Rain 1774 Fold Paper Strips 1803 Box Art 1810 Covering 1813 Overlapped Shapes 1819 Disks 1834 线段处理 1843 Shire 1851 Map 1871 Bullet Hole 1873 The Fortified Forest 1875 Robot 1877 Flooded! 1881 Sail Race 1899 Farmer Bill's Problem 1902 Illumination 1912 A highway and the seven dwarfs 1921 Paper Cut 1927 Area in Triangle 1931 Biometrics 1937 Balanced Food 1939 Diplomatic License

1940 Polygon Programming with Ease 1956 Pumps and Pipes 1971 Parallelogram Counting 1981 Circle and Points 1982 Water Tank 2007 Scrambled Polygon 2012 Triangle Cuts 2016 Ink Blots 2026 As the Crow Flies 2031 Building a Space Station 2036 I Conduit! 2043 Area of Polygons 2048 Monster Trap 2053 Square 2066 Minimax Triangulation 2069 Super Star 2074 Line of Sight 2079 Triangle 2087 Petanque 2098 Ellipse 2130 Jogging 2149 Inherit the Spheres 2150 Crossing Prisms 2164 Find the Border 2165 Gunman 2172 Bricks 2177 Ghost Busters 2284 That Nice Euler Circuit 2621 Parallelepiped 2622 Convex hull 2686 Traveling by Stagecoach 2687 Earth Observation with a Mobile Robot Team 2747 Shy Polygons 2839 Convex Hull and Triangle 2932 Coneology 2954 Triangle 3011 Secrets in Shadows 3129 How I Wonder What You Are! 3130 How I Mathematician Wonder What You Are! 3135 Polygons on the Grid 3334 Connected Gheeves 3335 Rotating Scoreboard 3347 Kadj Squares 3384 Feng Shui

3407 Brookebond s'en va en guerre... 3410 Split convex polygon 3608 Bridge Across Islands ZOJ zoj 相关练习题 1597 1608 1648 1683 1910 2102 2157 2318 2335 2347 2352 2361 2370 2375 2403 2015(中欧 1999 正赛) 2107(浙江 2004 省赛) 2228(北京 2004 预赛题,难) 2234(北京 2004 预赛题) 2214(北京 2004 正赛题,费马点,知道该知识点=〉易解,否则=〉不可能) 2394(上海 2004 正赛题) 主要内容(仔细核对,看看自己哪些未掌握) : 判断线段相交; 判断直线相交; 判断点是否在多边形内; 求凸包; 凸多边形面积计算; 矩形的交与并(扫描法) ; 已知三点求三角形面积(包括海伦公式)和重心; 已知三点求外接圆和内接圆圆心、半径、面积 ; 最近点对问题; 最远点对问题; 点集或图形集合的最小覆盖圆; 点集或图形集合的最小覆盖矩形; 三角剖分; 费尔马点的计算;


赞助商链接
相关文章:
ACM 计算几何 最小圆覆盖算法
ACM 计算几何 最小圆覆盖算法_初二数学_数学_初中教育_教育专区。最小圆覆盖...如果添加的点 i 在圆内,不动,否则: 的最小圆: 的最小圆, j=2~I问题...
浅谈ACM ICPC的题目风格和近几年题目的发展&&2005年第2...
计算几何一直是 ACM ICPC 里面的难题。不仅编程困难,更由于精度问题导致 非常难...总结和一些预计 基本上,实现起来不算太复杂的多项式时间复杂度的算法都可以出成...
ACM经典训练
ACM训练计划 3页 免费 ACM大赛训练题 9页 1下载券...ZOJ 题目分类 初学者题: 1001 1037 1048 1049 ...计算几何 容易: 1319, 1654, 1673, 1675, 1836,...
HUNAN UNIVERSITY ACMICPC Judge Online题目分类
HUNAN UNIVERSITY ACMICPC Judge Online题目分类_理学_高等教育_教育专区。HUNAN ...计算几何 11106 一般 概率 11109 简单 二叉树遍历 11100 一般 卡特兰数和大数...
acm常用模板
2. 几何题注意多测试不对称数据. 3. 整数几何注意...} 27 Acm 常用算法模板 //计算直线与平面交点,注意...一共 n-2 个三角形正好是多连形的一个划分,分别...
ACM 进阶之路
ACM 进阶之路一位高手的建议: 行以内的程序不用...问题 Polya 定理 计算几何 / 解析几何 计算几何的...创意简历模板汇集 推理型题分析与总结文档贡献者 stuq...
ACM模板
("%d\n",ans); } return 0; } 二、计算几何 1、两个凸多边形相交的面积...问题 <2>2-SUM 问题 <3>序列划分问题(单调队列优化) 6.剖分问题(多边形剖...
ACM竞赛简介和入门
主流的算法 分类分类为: 1.搜索 //回溯 搜索...计算几何 //凸壳、同等安置矩形的并 凸壳、 计算...ACM 感兴趣,在 poj 上做了 些题之后觉得有兴趣做...
acm icpc基础入门
问题 Polya 定理 计算几何 / 解析几何 计算几何的...acm/primer/2010/0531/220.html 参加 ACM 比赛所...教学总结精品范文 小学五年级英语教学工作总结 大学教师...
ACM国际大学生程序设计竞赛简介
ACM国际大学生程序设计竞赛简介_学习计划_计划/解决方案...计算几何题目难度不会很大,但也永远不会成为最弱...创意简历模板汇集 推理型题分析与总结文档贡献者 细节...
更多相关标签: