-
Notifications
You must be signed in to change notification settings - Fork 1
/
143.cc
115 lines (100 loc) · 2.8 KB
/
143.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cmath>
#include <iomanip>
#include <iostream>
enum {
#ifdef ONLINE_JUDGE
DEBUG = 0,
#else
DEBUG = 1,
#endif
};
#define LOG \
if (DEBUG) \
std::cerr
struct Point {
Point(double x_, double y_) : x(x_), y(y_) {}
Point() : Point(0, 0) {}
double x, y;
static const Point ZERO;
};
const Point Point::ZERO;
std::istream& operator>>(std::istream& in, Point& point) {
return in >> point.x >> point.y;
}
std::ostream& operator<<(std::ostream& out, const Point& point) {
return out << point.x << ' ' << point.y;
}
bool operator==(const Point& p, const Point& q) {
return p.x == q.x && p.y == q.y;
}
bool operator!=(const Point& p, const Point& q) { return !(p == q); }
bool IsApprox(double x, double y) { return ::fabs(x - y) < 1e-8; }
Point operator-(const Point& p, const Point& q) {
return Point(p.x - q.x, p.y - q.y);
}
double DotProduct(const Point& p, const Point& q) {
return p.x * q.x + p.y * q.y;
}
double CrossProduct(const Point& p, const Point& q) {
return p.x * q.y - p.y * q.x;
}
bool IsInsideOrOnBorder(const Point triangle[], const Point& point) {
// Test if it is on the border.
for (auto i = triangle, j = i + 1; j != triangle + 4; ++i, ++j) {
Point segment = *j - *i;
Point vector = point - *i;
// Special case where triangle is not a proper triangle.
if (segment == Point::ZERO) {
if (vector == Point::ZERO) {
return true;
} else {
continue;
}
}
double product = CrossProduct(segment, vector);
if (IsApprox(product, 0)) {
double dot = DotProduct(segment, vector);
if (0 <= dot && dot <= DotProduct(segment, segment)) {
return true;
}
}
}
// Test if it is inside.
enum { NONE, POS, NEG, } prev = NONE, curr = NONE;
for (auto i = triangle, j = i + 1; j != triangle + 4; ++i, ++j) {
Point segment = *j - *i;
Point vector = point - *i;
double product = CrossProduct(segment, vector);
if (IsApprox(product, 0)) {
return false;
}
curr = product > 0 ? POS : NEG;
if (prev != NONE && prev != curr) {
return false;
}
prev = curr;
}
return true;
}
int main() {
for (Point triangle[4];
std::cin >> triangle[0] >> triangle[1] >> triangle[2] &&
(triangle[0] != Point::ZERO || triangle[1] != Point::ZERO ||
triangle[2] != Point::ZERO);) {
triangle[3] = triangle[0];
LOG << "triangle: " << triangle[0] << ' ' << triangle[1] << ' '
<< triangle[2] << std::endl;
int num_trees = 0;
for (double x = 1; x <= 99; x += 1) {
for (double y = 1; y <= 99; y += 1) {
Point point(x, y);
if (IsInsideOrOnBorder(triangle, point)) {
LOG << "point: " << point << std::endl;
++num_trees;
}
}
}
std::cout << std::setw(4) << num_trees << std::endl;
}
return 0;
}