# Poj Solution 1228

```http://poj.org/problem?id=1228

import java.io.IOException;

public class Main {

class Point {
int x;
int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

public static void main(String[] args) throws NumberFormatException,
IOException {
Main main = new Main();
System.in));
Point[] p;
Point[] ch;
int x, y;
String[] s;
int len;
int t;
boolean b;
for (int i = 0; i < n; i++) {
p = new Point[m];
for (int j = 0; j < m; j++) {
x = Integer.parseInt(s);
y = Integer.parseInt(s);
p[j] = main.new Point(x, y);
}
if (m <= 5) {
System.out.println("NO");
} else {
ch = new Point[m];
len = 0;
len = Graham_scan(p, ch, m);
b = false;
t = 0;
for (int j = 0; j < len - 2; j++) {
if (!AtOneLine(ch[j], ch[j + 1], ch[j + 2])) {
b = true;
break;
}
}
if (b) {
for (int j = 0; j < len - 1; j++) {
for (int k = 0; k < m; k++) {
if (AtOneLine(ch[j], ch[j + 1], p[k])) {
t++;
}
}
if (t < 3) {
b = false;
break;
}
t = 0;
}
}
if (b) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}

public static boolean AtOneLine(Point p1, Point p2, Point p3) {
return ((p1.x - p2.x) * (p1.y - p3.y) == (p1.x - p3.x) * (p1.y - p2.y));
}

public static double multiply(Point p1, Point p2, Point p0) {
return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));

}

public static double distance(Point p1, Point p2) {
return (Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y)
* (p1.y - p2.y)));
}

public static int Graham_scan(Point[] PointSet, Point[] ch, int n) {
int i, j, k = 0, top = 2;
Point tmp;
for (i = 1; i < n; i++)
if ((PointSet[i].y < PointSet[k].y)
|| ((PointSet[i].y == PointSet[k].y) && (PointSet[i].x < PointSet[k].x)))
k = i;
tmp = PointSet;
PointSet = PointSet[k];
PointSet[k] = tmp;
for (i = 1; i < n - 1; i++) {
k = i;
for (j = i + 1; j < n; j++)
if ((multiply(PointSet[j], PointSet[k], PointSet) > 0)
|| ((multiply(PointSet[j], PointSet[k], PointSet) == 0) && (distance(
PointSet, PointSet[j]) < distance(
PointSet, PointSet[k]))))
k = j;
tmp = PointSet[i];
PointSet[i] = PointSet[k];
PointSet[k] = tmp;
}
ch = PointSet;
ch = PointSet;
ch = PointSet;
for (i = 3; i < n; i++) {
while (top > 0 && multiply(PointSet[i], ch[top], ch[top - 1]) >= 0)
top--;
ch[++top] = PointSet[i];
}