1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111

#include <algorithm>
#include <iostream>
#include <climits>
#include <tuple>
#include <cmath>
using namespace std;
constexpr auto EPS = numeric_limits<double>::epsilon();

struct point {
	int x, y;
	point() { x = y = 0; }
	point(int _x, int _y) : x(_x), y(_y) {}
	bool operator < (point p) const {
		return (x == p.x && y < p.y) || x < p.x;
	}
	bool operator == (point p) const {
		return x == p.x && y == p.y;
	}
};

double dist(point& p1, point& p2) {
	return hypot(p1.x - p2.x, p1.y - p2.y);
}

struct vec {
	int x, y;
	vec(int _x, int _y) : x(_x), y(_y) {}
};

vec to_vec(point a, point b) {
	return vec(b.x - a.x, b.y - a.y);
}

int dot(vec a, vec b) {
	return (a.x * b.x + a.y * b.y);
}

int norm_sq(vec v) {
	return v.x * v.x + v.y * v.y;
}

int cross(vec a, vec b) {
	return a.x * b.y - a.y * b.x;
}

double angle(point a, point o, point b) {
	vec oa = to_vec(o, a), ob = to_vec(o, b);
	return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
}

bool ccw(point p, point q, point r) {
	return cross(to_vec(p, q), to_vec(p, r)) > 0;
}

double angle(point a, point o, point b) {
	vec oa = to_vec(o, a), ob = to_vec(o, b);
	return acos(dot(oa, ob) / (sqrt(norm_sq(oa)) * sqrt(norm_sq(ob))));
}

struct line {
	int a, b, c;
	bool operator < (const line& l) const {
		return tie(a, b, c) < tie(l.a, l.b, l.c);
	}
};

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

line to_line(point p1, point p2) {
	int a = p2.y - p1.y, b = p1.x - p2.x, c = p1.y * p2.x - p1.x * p2.y;
	int d = gcd(gcd(abs(a), abs(b)), abs(c));
	return { a / d, b / d, c / d };
}

double point_to_line(point p, line l) {
	return abs(l.a * p.x + l.b * p.y + l.c) / hypot(l.a, l.b);
}

line perp_bi(point p1, point p2) {
	int a = 2 * (p2.x - p1.x), b = 2 * (p2.y - p1.y), c = -a * (p1.x + p2.x) / 2 - b * (p1.y + p2.y) / 2;
	int d = gcd(gcd(abs(a), abs(b)), abs(c));
	return { a / d, b / d, c / d };
}

point reflect(point p, line l) {
	int x = p.x * (l.b * l.b - l.a * l.a) - 2 * l.a * (l.b * p.y + l.c);
	int y = p.y * (l.a * l.a - l.b * l.b) - 2 * l.b * (l.a * p.x + l.c);
	int d = l.a * l.a + l.b * l.b;
	if (x % d && y % d) return { 10001, 10001 };
	else return { x / d, y / d };
}

struct seg {
	point p1, p2;
	seg(point _p1, point _p2) : p1(_p1), p2(_p2) {}
};

line to_line(seg s) {
	return to_line(s.p1, s.p2);
}

double point_to_seg(point p, seg s) {
	int a = norm_sq(to_vec(s.p1, s.p2)), b = norm_sq(to_vec(p, s.p1)), c = norm_sq(to_vec(p, s.p2));
	if (a + b > c && a + c > b) return point_to_line(p, to_line(s));
	else return min(dist(p, s.p1), dist(p, s.p2));
}

bool seg_isect(seg a, seg b) {
	return ccw(a.p1, a.p2, b.p1) * ccw(a.p1, a.p2, b.p2) <= 0 && ccw(b.p1, b.p2, a.p1) * ccw(b.p1, b.p2, a.p2) <= 0);
}