题目地址：http://poj.org/problem?id=1228
因为每条边至少要有3个点，所以要判断每条边有几个点共线
方法是求出凸包的点，再任意枚举凸包上相邻的两个点，再遍历其他点利用叉积看是否与它共线
要注意：但点数小于6是肯定不可能的，还有所有点都共线的情况也是不可能的
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define Vector Point
const double EPS=1e-6;
int Sign(double x){if(fabs(x)<EPS) return 0;return x < 0 ? -1 : 1 ;
}
struct Point{double x,y;Point(double x,double y):x(x),y(y){}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}bool operator < (const Point& p) const {if(Sign(x-p.x)==0) return y<p.y;return x<p.x;}
};
double cross(const Vector& p1,const Vector& p2){return p1.x*p2.y-p1.y*p2.x;
}vector<Point> points;
vector<Point> stack; bool Graham()
{if(points.size()<6) return false; //少于6个点是不可能的 stack.clear();sort(points.begin(),points.end());stack.push_back(points[0]);stack.push_back(points[1]);int n=points.size();for(int i=2;i<n;i++){while(stack.size()>1){Point p2=*(stack.end()-1);Point p1=*(stack.end()-2);if(Sign(cross(p2-p1,points[i]-p2))<0)stack.pop_back();else break;}stack.push_back(points[i]);}int size=stack.size();stack.push_back(points[n-2]);for(int i=n-3;i>=0;i--){while(stack.size()>size){Point p2=*(stack.end()-1);Point p1=*(stack.end()-2);if(Sign(cross(p2-p1,points[i]-p2))<0)stack.pop_back();else break;}stack.push_back(points[i]);}stack.pop_back();return true;
}
int main()
{int T;cin>>T;while(T--){int n;cin>>n;points.clear();for(int i=0;i<n;i++){int x,y;cin>>x>>y;points.push_back(Point(x,y));}int ok=0;if(Graham())for(int i=0;i<stack.size();i++){Point p1=stack[i],p2=stack[(i+1)%stack.size()];ok=0;for(int j=0;j<stack.size();j++){if(j==i||j==((i+1)%stack.size())) continue;if(Sign(cross(p2-p1,stack[j]-p1))==0) ok++; //若有共线的点就加一 }if(ok==0||ok==stack.size()-2) break;}cout<<((ok==0||ok==stack.size()-2)?"NO":"YES")<<endl;} //不存在共线点||所有点都共线 return 0;
}