-
Notifications
You must be signed in to change notification settings - Fork 0
/
MPOLY-polygon.cpp
64 lines (45 loc) · 1.23 KB
/
MPOLY-polygon.cpp
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
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
Point operator-(const Point& p) const { return Point{x - p.x, y - p.y}; }
int cross(const Point& p) const { return x * p.y - y * p.x; }
bool operator<(const Point& p) const { return cross(p) > 0; }
};
int N, memo[101][101];
vector<Point> points;
int dp(int p, int prev_idx) {
if (memo[p][prev_idx] != -1) return memo[p][prev_idx];
int ret = 0;
const Point& curr = points[p];
const Point& prev = points[prev_idx];
for (int i = p + 1; i < (int)points.size(); i++) {
const Point& next = points[i];
Point prev_curr = curr - prev;
Point curr_next = next - curr;
if (prev_curr.cross(curr_next) > 0) {
ret = max(ret, 1 + dp(i, p));
}
}
return memo[p][prev_idx] = ret;
}
void solve() {
memset(memo, -1, sizeof memo);
points = vector<Point>(N);
for (int i = 0; i < N; i++) {
cin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.end());
points.insert(points.begin(), Point{0, 0});
int ans = 0;
for (int i = 1; i < (int)points.size(); i++) {
ans = max(ans, 1 + dp(i, 0));
}
cout << (1 + ans) << endl;
}
int main() {
while (scanf("%d", &N) == 1 && N > 0) {
solve();
printf("\n");
}
}