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/  
這些題的解題報告
http://old.blog.edu.cn/user3/Hailer/archives/2008/2158935.shtml

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正賽題)

 

主要內容（仔細核對，看看自己哪些未掌握）：

 

判斷線段相交；

判斷直線相交；

判斷點是否在多邊形內；

求凸包；

凸多邊形面積計算；

矩形的交與并（掃描法）；

已知三點求三角形面積（包括海倫公式）和重心；

已知三點求外接圓和內接圓圓心、半徑、面積 ；

最近點對問題；

最遠點對問題；

點集或圖形集合的最小覆蓋圓；

點集或圖形集合的最小覆蓋矩形；

三角剖分；

費爾馬點的計算；