SPOJ 4061 - MPOLY - Polygon

There are N points in a plane whose coordinates are natural numbers. A convex polygon with maximal number of vertices is a convex polygon whose vertices are some of given points and the origin having maximal possible number of vertices. Origin, i.e. point with coordinates (0,0), must be one of vertices of a convex polygon with maximal number of vertices.

Write a program that will determine number of vertices in such polygon.

A polygon is convex if every line segment whose endpoints are inside that polygon is also completely inside it. Consecutive edges of a polygon must not be parallel.

Input

The first line of input file contains a natural number N, 2 ≤ N ≤ 100, a number of given points.

Each of the following N lines contains two natural numbers X and Y, 1 ≤ X ≤ 100, 1 ≤ Y ≤ 100, separated by a space character, coordinates of one point.

All points will be different.

Output

The first and only line of output file should contain number of vertices of convex polygon with maximal number of vertices. Note: the result will always be at least 3.

Sample

plaintext

POLYGON.IN

5
4 2
2 2
2 3
3 2
3 1

POLYGON.OUT

4
 
POLYGON.IN

8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10

POLYGON.OUT

8
 
POLYGON.IN

10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9

POLYGON.OUT

7
Explanation for test data #2 (coordinates of polygon)

2 8
3 9
8 10
9 10
10 8
10 3
9 2
0 0

Solution

Dynamic Programming, the strategy is quite similar to Graham Scan.

let $P = \{ (x_i, y_i), i \in 1..n \}$ represents the given points.

let $F(i, d)$ represents the max number of points which starts from $P_i$ and can be connected as part of a convex hull, while $d = (dx, dy)$ represets the initialized direction of expected path.

$F(i, d) = Max\{F(j, P_j - P_i) + 1 | d \times (P_j - P_i) > 0 \land (P_j - P_i) \times (O - P_i) > 0\}$

To make it easy to implement and not enumerate all states in searching space, I used memorized search.

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {

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

typedef struct {

  int x;
  int y;

} vector;

vector point_new(int x, int y) {

  vector v;

  v.x = x;
  v.y = y;

  return v;
}

vector vector_new(int x, int y) {

  int d = gcd(x, y);

  if (d < 0) {

    d = -d;
  }

  return (d == 0) ? point_new(x, y) : point_new(x / d, y / d);
}

vector vector_sub(vector a, vector b) {

  return vector_new(a.x - b.x, a.y - b.y);
}

int vector_cross(vector a, vector b) {

  return a.x * b.y - a.y * b.x;
}

#define MAX_N 100
#define MAX_X 100
#define MAX_Y 100

int n;

vector p[MAX_N];

int f[MAX_N][MAX_X + MAX_X + 1][MAX_Y + MAX_Y + 1];

int dp(int current, vector direction) {

  int i, max_next = -1;

  vector next;
  vector to_origin = point_new(-p[current].x, -p[current].y);


  if (-1 == f[current][direction.x + MAX_X][direction.y + MAX_Y]) {

    f[current][direction.x + MAX_X][direction.y + MAX_Y] = 1;

    for (i = 0; i < n; i++) {

      if (i != current) {

        next = vector_sub(p[i], p[current]);

        if (vector_cross(direction, next) > 0
          && vector_cross(next, to_origin) > 0) {

          if (dp(i, next) + 1 > f[current][direction.x + MAX_X][direction.y + MAX_Y]) {

            f[current][direction.x + MAX_X][direction.y + MAX_Y] = dp(i, next) + 1;
          }
        }
      }
    }
  }

  return f[current][direction.x + MAX_X][direction.y + MAX_Y];
}

void init() {

  int i;

  scanf("%d", &n);

  for (i = 0; i < n; i++) {

    scanf("%d%d", &p[i].x, &p[i].y);
  }
}

void solve() {

  int i, x, y, ans = -1;

  for (i = 0; i < n; i++) {
    for (x = -MAX_X; x <= MAX_X; x++) {
      for (y = -MAX_Y; y <= MAX_Y; y++) {
        f[i][x + MAX_X][y + MAX_Y] = -1;
      }
    }
  }

  for (i = 0; i < n; i++) {

    if ((ans == -1) || (dp(i, vector_new(p[i].x, p[i].y)) > ans)) {

      ans = dp(i, vector_new(p[i].x, p[i].y));
    }
  }

  printf("%d\n", ans + 1);
}

int main(int argc, char **argv) {

  init();
  solve();
  return 0;
}