Geometry Problem List by Shahriar Rouf Nafi

1

Section

OJ

Number

Link

Name

Difficulty (1e to 5h)

Description

Discussion

2

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

uva

190

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

3

Circumcenter

3

191

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

3

LS & Solid Rect Isect

4

378

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

2

L & L Isect

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 Isect

7

460

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

1

Rect & Rect Overlap

8

476

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

1

9

477

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

1

10

478

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

2

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

14

10709

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

4

15

10725

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

3

16

10979

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

5

intersections and Floyd Warshall

17

Vector2D / Vector3D

uva

190

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

3

18

191

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

3

19

378

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

2

20

453

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

Intersecting Circles

3

Pain with precision

21

10242

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

1

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

5

3D

26

1703

2

27

1710

1

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

2

31

10286

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

1

32

10287

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

3

BS

33

10289

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

4

BS

34

10353

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

4

BS

35

10402

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

5

36

10481

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

4

BS

37

11009

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

4

BS => TLE, formula must

38

Binary Search A.K.A. Bisection Method

uva

10287

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

2

39

10289

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

3

40

10322

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

4

41

10341

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

1

42

10345

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

Cricket/Football Goes Down

3

43

10353

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

4

44

10372

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

2

45

10386

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

3

46

10398

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

2

47

10481

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

4

48

10566

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

2

49

10631

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

5

Normals of Ellipse - 2 cases

50

10668

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

2

51

10695

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

4

Many Cases! -- Understanding Advantage of Obtuse angle

52

Geodesic Distance

links

-

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

53

uva

10517

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

54

10598

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

55

10809

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

56

Convex Hull

links

-

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

57

-

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

58

uva

109

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

59

132

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

60

218

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

61

361

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

62

596

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

63

681

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

64

811

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

65

819

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

66

10065

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

67

10078

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

68

10089

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

69

10135

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

70

10173

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

71

10256

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

4

72

Miscellaneous

uva

10095

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

4

73

10209

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

2

74

10210

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

75

10215

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

1

Differentiation is enough

76

10216

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

The Optimal Coffee Shop

4

Fermat Point

77

-

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

78

10221

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

1

79

10228

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

3

Greedy Local Search

80

10242

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

1

81

10245

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

3

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

82

-

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

83

-

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

84

10251

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

3

85

10478

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

2

86

11123

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

87

11186

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

3

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

88

11529

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

5

cumulative + lower_bound

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106