Geometry Problem List by Shahriar Rouf Nafi


1	Section	OJ	Number	Link	Name	Difficulty 1 = easiest 5 = hardest	Description / Solution hint	Links

2	Circle, Triangle, Rectangle, Square, Intersections, Overlaps, Point-in-Objects, Adhocs	uva	190	http://uva.onlinejudge.org/external/1/190.html		3	Circumcenter
3	191	http://uva.onlinejudge.org/external/1/191.html		3	Line Segment and Solid Rectangle Intersection
4	378	http://uva.onlinejudge.org/external/3/378.html		2	Line, Line Intersection
5	438	http://uva.onlinejudge.org/external/4/438.html		1	Easier than 190, only Circumference
6	453	http://uva.onlinejudge.org/external/4/453.html		3	Circle & Circle Intersection
7	460	http://uva.onlinejudge.org/external/4/460.html		1	Rectangle, Rectangle Overlap
8	476	http://uva.onlinejudge.org/external/4/476.html		1	Point in Rectangles
9	477	http://uva.onlinejudge.org/external/4/477.html		1	Point in Rectangles, Circles
10	478	http://uva.onlinejudge.org/external/4/478.html		1	Point in Rectangles, Circles, Triangles
11	10175	http://uva.onlinejudge.org/external/101/10175.html	Sphere	2	Formula needed or do volume integration to find the formula
12	10522	http://uva.onlinejudge.org/external/105/10522.html	Height to Area	2	All three heights of a triangle are given. Find the area.	http://isolvedaproblem.blogspot.com/2012/06/height-to-area-uva-10522.html
13	10573	http://uva.onlinejudge.org/external/105/10573.html		1	Adhoc, simple calculation. Understanding when 1 info is enough
14	10709	http://uva.onlinejudge.org/external/107/10709.html		3	Distance between Line/Line-segment
15	10725	http://uva.onlinejudge.org/external/107/10725.html		3	Largest square in a triangle
16	10979	http://uva.onlinejudge.org/external/109/10979.html		5	How many triangles in a list of line-segments. Intersections and Floyd Warshall
17	Vector2D / Vector3D	uva	190	http://uva.onlinejudge.org/external/1/190.html		3	Circumcenter
18	191	http://uva.onlinejudge.org/external/1/191.html		3	Line Segment and Solid Rectangle Intersection
19	378	http://uva.onlinejudge.org/external/3/378.html		2	Line, Line Intersection
20	453	http://uva.onlinejudge.org/external/4/453.html	Intersecting Circles	3	Circle & Circle Intersection Pain with precision
21	10242	http://uva.onlinejudge.org/external/102/10242.html		1	Given coordinates A B C of ABCD parallelogram, find D.
22	10674	http://uva.onlinejudge.org/external/106/10674.html		4	Tangents of two circles - 5 cases
23	10709	http://uva.onlinejudge.org/external/107/10709.html		4	Better to use vector here
24	11580	http://uva.onlinejudge.org/external/115/11580.html		5	3D, Although very hard, it is worth noticing its figure. It might help understanding latitude, longitude.
25	timus	1697	http://acm.timus.ru/problem.aspx?num=1697	Sniper Shot	5	3D. Earliest visible point in a line segment AB from a point S.
26	1703	http://acm.timus.ru/problem.aspx?num=1703	Robotic Arm	2	2D
27	1710	http://acm.timus.ru/problem.aspx?num=1710	Boris, You Are Wrong!	1	2D. Understanding of triangle congruence
28	tju	3114			3	3D
29	ipsc	L(2012)	http://ipsc.ksp.sk/contests/ipsc2012/real/problems/l.html		5	2D, Circle & polygon common area, Hyperbola & Rectangle common area, integral of sqrt(x^2 - a^2)
30	Packing Problems	uva	10283	http://uva.onlinejudge.org/external/102/10283.html	The Kissing Circles	2	Circles in a circle. Closed form formula
31	10286	http://uva.onlinejudge.org/external/102/10286.html		1	Square in a regular pentagon. Closed form formula
32	10287	http://uva.onlinejudge.org/external/102/10287.html		3	Circles in a regular hexagon. Closed form formula + Binary Search
33	10289	http://uva.onlinejudge.org/external/102/10289.html		4	Equilateral triangles in a square. Closed form formula + Binary Search
34	10345	http://uva.onlinejudge.org/external/103/10345.html	Cricket/Football Goes Down	3	Squares in a circle. Closed form formula + Binary Search
35	10353	http://uva.onlinejudge.org/external/103/10353.html		4	5, 8 circles in a regular hexagon. No closed form formula. Must do Binary Search
36	10386	http://uva.onlinejudge.org/external/103/10386.html		3	Circles in an equilateral triangle. Binary search.
37	10402	http://uva.onlinejudge.org/external/104/10402.html		5	Covering equilateral triangle with Squares. Binary Search
38	10481	http://uva.onlinejudge.org/external/104/10481.html		4	Triangles in a circle. Formula + Binary Search
39	11009	http://uva.onlinejudge.org/external/110/11009.html		4	Binary Search => TLE, Must derive formula
40	Binary Search		10322	http://uva.onlinejudge.org/external/103/10322.html		4	Finding Binary search logic is tricky
41	10341	http://uva.onlinejudge.org/external/103/10341.html		1	Finding solution to F(x) = 0. F(x) is continous, but contains many transcendental functions.
42	10372	http://uva.onlinejudge.org/external/103/10372.html		2	Formula maybe feasbile, but Binary Search simplifies a lot.
43	10398	http://uva.onlinejudge.org/external/103/10398.html		2	Solve 1 + x^4 = x^5 using Binary Search.
44	10566	http://uva.onlinejudge.org/external/105/10566.html		2	Formula maybe feasbile, but Binary Search simplifies a lot.
45	10631	http://uva.onlinejudge.org/external/106/10631.html		5	Normals of Ellipse - 2 cases
46	10668	http://uva.onlinejudge.org/external/106/10668.html		2	Arcs, Chords
47	10695	http://uva.onlinejudge.org/external/106/10695.html		4	Many Cases! -- Understanding Advantage of Obtuse angle
48	Geodesic Distance	uva	10517	http://uva.onlinejudge.org/external/105/10517.html			North-East-South-West (n,n,n,m), but same place! Lattitude?	http://en.wikipedia.org/wiki/Great-circle_distance
49	10598	http://uva.onlinejudge.org/external/105/10598.html			North-East-South (n,n,n), but same place! Lattitude?
50	10809	http://uva.onlinejudge.org/external/108/10809.html		5	Find the northmost/southmost point in the shortest path between 2 points in the globe. Idea? Formulate Parametric equation + Differentiation.
51	Convex Hull	links	-				http://www.cs.ucf.edu/courses/cot5520/GScanJMarch.ppt
52	-				http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm
53	uva	109	http://uva.onlinejudge.org/external/1/109.html
54	132	http://uva.onlinejudge.org/external/1/132.html
55	218	http://uva.onlinejudge.org/external/2/218.html
56	361	http://uva.onlinejudge.org/external/3/361.html
57	596	http://uva.onlinejudge.org/external/5/596.html
58	681	http://uva.onlinejudge.org/external/6/681.html
59	811	http://uva.onlinejudge.org/external/8/811.html
60	819	http://uva.onlinejudge.org/external/8/819.html
61	10065	http://uva.onlinejudge.org/external/100/10065.html
62	10078	http://uva.onlinejudge.org/external/100/10078.html
63	10089	http://uva.onlinejudge.org/external/100/10089.html
64	10135	http://uva.onlinejudge.org/external/101/10135.html
65	10173	http://uva.onlinejudge.org/external/101/10173.html
66	10256	http://uva.onlinejudge.org/external/102/10256.html		4
67	Miscellaneous	uva	10095	http://uva.onlinejudge.org/external/100/10095.html		4
68	10209	http://uva.onlinejudge.org/external/102/10209.html		2	Circle, Triangle Formulas 1/2absin(T), 1/2T*r^2 etc
69	10210	http://uva.onlinejudge.org/external/102/10210.html
70	10215	http://uva.onlinejudge.org/external/102/10215.html		1	Differentiation is enough
71	10216	http://uva.onlinejudge.org/external/102/10216.html	The Optimal Coffee Shop	4	Fermat Point. Find P inside ABC triangle such that APB = BPC = CPA = 120 degrees. Special case when one angle is > 120 degrees.	http://en.wikipedia.org/wiki/Fermat_point
72	10221	http://uva.onlinejudge.org/external/102/10221.html		1
73	10228	http://uva.onlinejudge.org/external/102/10228.html		3	Gradient Descent in 2D space
74	10242	http://uva.onlinejudge.org/external/102/10242.html		1	Given coordinates A B C of ABCD parallelogram, find D.
75	10245	http://uva.onlinejudge.org/external/102/10245.html		3	Closest Pair - Div & Conq - O(n lg n)
76	-				http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
77	-				http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
78	10251	http://uva.onlinejudge.org/external/102/10251.html		3
79	10478	http://uva.onlinejudge.org/external/104/10478.html		2	Formula.
80	11123	http://uva.onlinejudge.org/external/111/11123.html			How many trapezoids among N points
81	11186	http://uva.onlinejudge.org/external/111/11186.html		3	looks like geo, but mainly it needs proper use of cumulative arrays
82	11529	http://uva.onlinejudge.org/external/115/11529.html		5	cumulative + lower_bound
83
84
85
86
87
88
89
90
91

1

Section

OJ

Number

Link

Name

Difficulty
1 = easiest
5 = hardest

Description / Solution hint

Links

2

Circle, Triangle, Rectangle, Square, Intersections, Overlaps, Point-in-Objects, Adhocs

uva

190

http://uva.onlinejudge.org/external/1/190.html

3

Circumcenter

3

191

http://uva.onlinejudge.org/external/1/191.html

3

Line Segment and Solid Rectangle Intersection

4

378

http://uva.onlinejudge.org/external/3/378.html

2

Line, Line Intersection

5

438

http://uva.onlinejudge.org/external/4/438.html

1

Easier than 190, only Circumference

6

453

http://uva.onlinejudge.org/external/4/453.html

3

Circle & Circle Intersection

7

460

http://uva.onlinejudge.org/external/4/460.html

1

Rectangle, Rectangle Overlap

8

476

http://uva.onlinejudge.org/external/4/476.html

1

Point in Rectangles

9

477

http://uva.onlinejudge.org/external/4/477.html

1

Point in Rectangles, Circles

10

478

http://uva.onlinejudge.org/external/4/478.html

1

Point in Rectangles, Circles, Triangles

11

10175

http://uva.onlinejudge.org/external/101/10175.html

Sphere

2

Formula needed or do volume integration to find the formula

12

10522

http://uva.onlinejudge.org/external/105/10522.html

Height to Area

2

All three heights of a triangle are given. Find the area.

http://isolvedaproblem.blogspot.com/2012/06/height-to-area-uva-10522.html

13

10573

http://uva.onlinejudge.org/external/105/10573.html

1

Adhoc, simple calculation. Understanding when 1 info is enough

14

10709

http://uva.onlinejudge.org/external/107/10709.html

3

Distance between Line/Line-segment

15

10725

http://uva.onlinejudge.org/external/107/10725.html

3

Largest square in a triangle

16

10979

http://uva.onlinejudge.org/external/109/10979.html

5

How many triangles in a list of line-segments.
Intersections and Floyd Warshall

17

Vector2D / Vector3D

uva

190

http://uva.onlinejudge.org/external/1/190.html

3

Circumcenter

18

191

http://uva.onlinejudge.org/external/1/191.html

3

Line Segment and Solid Rectangle Intersection

19

378

http://uva.onlinejudge.org/external/3/378.html

2

Line, Line Intersection

20

453

http://uva.onlinejudge.org/external/4/453.html

Intersecting Circles

3

Circle & Circle Intersection
Pain with precision

21

10242

http://uva.onlinejudge.org/external/102/10242.html

1

Given coordinates A B C of ABCD parallelogram, find D.

22

10674

http://uva.onlinejudge.org/external/106/10674.html

4

Tangents of two circles - 5 cases

23

10709

http://uva.onlinejudge.org/external/107/10709.html

4

Better to use vector here

24

11580

http://uva.onlinejudge.org/external/115/11580.html

5

3D, Although very hard, it is worth noticing its figure. It might help understanding latitude, longitude.

25

timus

1697

http://acm.timus.ru/problem.aspx?num=1697

Sniper Shot

5

3D. Earliest visible point in a line segment AB from a point S.

26

1703

http://acm.timus.ru/problem.aspx?num=1703

Robotic Arm

2

2D

27

1710

http://acm.timus.ru/problem.aspx?num=1710

Boris, You Are Wrong!

1

2D. Understanding of triangle congruence

28

tju

3114

3

3D

29

ipsc

L(2012)

http://ipsc.ksp.sk/contests/ipsc2012/real/problems/l.html

5

2D, Circle & polygon common area, Hyperbola & Rectangle common area, integral of sqrt(x^2 - a^2)

30

Packing Problems

uva

10283

http://uva.onlinejudge.org/external/102/10283.html

The Kissing Circles

2

Circles in a circle.
Closed form formula

31

10286

http://uva.onlinejudge.org/external/102/10286.html

1

Square in a regular pentagon.
Closed form formula

32

10287

http://uva.onlinejudge.org/external/102/10287.html

3

Circles in a regular hexagon.
Closed form formula + Binary Search

33

10289

http://uva.onlinejudge.org/external/102/10289.html

4

Equilateral triangles in a square.
Closed form formula + Binary Search

34

10345

http://uva.onlinejudge.org/external/103/10345.html

Cricket/Football Goes Down

3

Squares in a circle.
Closed form formula + Binary Search

35

10353

http://uva.onlinejudge.org/external/103/10353.html

4

5, 8 circles in a regular hexagon.
No closed form formula. Must do Binary Search

36

10386

http://uva.onlinejudge.org/external/103/10386.html

3

Circles in an equilateral triangle.
Binary search.

37

10402

http://uva.onlinejudge.org/external/104/10402.html

5

Covering equilateral triangle with Squares.
Binary Search

38

10481

http://uva.onlinejudge.org/external/104/10481.html

4

Triangles in a circle.
Formula + Binary Search

39

11009

http://uva.onlinejudge.org/external/110/11009.html

4

Binary Search => TLE,
Must derive formula

40

Binary Search

10322

http://uva.onlinejudge.org/external/103/10322.html

4

Finding Binary search logic is tricky

41

10341

http://uva.onlinejudge.org/external/103/10341.html

1

Finding solution to F(x) = 0. F(x) is continous, but contains many transcendental functions.

42

10372

http://uva.onlinejudge.org/external/103/10372.html

2

Formula maybe feasbile, but Binary Search simplifies a lot.

43

10398

http://uva.onlinejudge.org/external/103/10398.html

2

Solve 1 + x^4 = x^5 using Binary Search.

44

10566

http://uva.onlinejudge.org/external/105/10566.html

2

Formula maybe feasbile, but Binary Search simplifies a lot.

45

10631

http://uva.onlinejudge.org/external/106/10631.html

5

Normals of Ellipse - 2 cases

46

10668

http://uva.onlinejudge.org/external/106/10668.html

2

Arcs, Chords

47

10695

http://uva.onlinejudge.org/external/106/10695.html

4

Many Cases! -- Understanding Advantage of Obtuse angle

48

Geodesic Distance

uva

10517

http://uva.onlinejudge.org/external/105/10517.html

North-East-South-West (n,n,n,m), but same place! Lattitude?

http://en.wikipedia.org/wiki/Great-circle_distance

49

10598

http://uva.onlinejudge.org/external/105/10598.html

North-East-South (n,n,n), but same place! Lattitude?

50

10809

http://uva.onlinejudge.org/external/108/10809.html

5

Find the northmost/southmost point in the shortest path between 2 points in the globe.
Idea? Formulate Parametric equation + Differentiation.

51

Convex Hull

links

-

http://www.cs.ucf.edu/courses/cot5520/GScanJMarch.ppt

52

-

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm

53

uva

109

http://uva.onlinejudge.org/external/1/109.html

54

132

http://uva.onlinejudge.org/external/1/132.html

55

218

http://uva.onlinejudge.org/external/2/218.html

56

361

http://uva.onlinejudge.org/external/3/361.html

57

596

http://uva.onlinejudge.org/external/5/596.html

58

681

http://uva.onlinejudge.org/external/6/681.html

59

811

http://uva.onlinejudge.org/external/8/811.html

60

819

http://uva.onlinejudge.org/external/8/819.html

61

10065

http://uva.onlinejudge.org/external/100/10065.html

62

10078

http://uva.onlinejudge.org/external/100/10078.html

63

10089

http://uva.onlinejudge.org/external/100/10089.html

64

10135

http://uva.onlinejudge.org/external/101/10135.html

65

10173

http://uva.onlinejudge.org/external/101/10173.html

66

10256

http://uva.onlinejudge.org/external/102/10256.html

4

67

Miscellaneous

uva

10095

http://uva.onlinejudge.org/external/100/10095.html

4

68

10209

http://uva.onlinejudge.org/external/102/10209.html

2

Circle, Triangle Formulas
1/2*a*b*sin(T), 1/2*T*r^2 etc

69

10210

http://uva.onlinejudge.org/external/102/10210.html

70

10215

http://uva.onlinejudge.org/external/102/10215.html

1

Differentiation is enough

71

10216

http://uva.onlinejudge.org/external/102/10216.html

The Optimal Coffee Shop

4

Fermat Point. Find P inside ABC triangle such that APB = BPC = CPA = 120 degrees.
Special case when one angle is > 120 degrees.

http://en.wikipedia.org/wiki/Fermat_point

72

10221

http://uva.onlinejudge.org/external/102/10221.html

1

73

10228

http://uva.onlinejudge.org/external/102/10228.html

3

Gradient Descent in 2D space

74

10242

http://uva.onlinejudge.org/external/102/10242.html

1

Given coordinates A B C of ABCD parallelogram, find D.

75

10245

http://uva.onlinejudge.org/external/102/10245.html

3

Closest Pair - Div & Conq - O(n lg n)

76

-

http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

77

-

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

78

10251

http://uva.onlinejudge.org/external/102/10251.html

3

79

10478

http://uva.onlinejudge.org/external/104/10478.html

2

Formula.

80

11123

http://uva.onlinejudge.org/external/111/11123.html

How many trapezoids among N points

81

11186

http://uva.onlinejudge.org/external/111/11186.html

3

looks like geo, but mainly it needs proper use of cumulative arrays

82

11529

http://uva.onlinejudge.org/external/115/11529.html

5

cumulative + lower_bound

83

84

85

86

87

88

89

90

91