题意：n个点，给定每个点的坐标，任选其中的三个点，并且由这三个点组成的三角形里不包含这些点，也就是说这些点严格控制在三角形外。保证解存在，输出其中任意一个解
解题思路：将n个点排序，选出最小的两个点，然后遍历枚举第三个点，因为是按照升序排列的，所以由这三个点组成的三角形一定是最小的，其余的点也就在三角形外，第三个点的判断条件就是是否共线，如果共线就不能组成三角形了
代码：
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> using namespace std; typedef long long int ll; struct P { ll x,y,id; }p[100005]; int n; bool cmp(P a,P b) { if(a.x==b.x)return a.y<b.y; return a.x<b.x; } bool judge(ll x,ll y)//用向量判断是否共线x1y2-x2y1=0 { if((p[1].x-p[0].x)*(y-p[1].y)-(x-p[1].x)*(p[1].y-p[0].y)==0)return false; return true; } int main() { while(scanf("%I64d",&n)==1) { for(ll i=0;i<n;i++) { scanf("%I64d%I64d",&p[i].x,&p[i].y); p[i].id=i+1; } sort(p,p+n,cmp); for(ll i=2;i<n;i++) { if(judge(p[i].x,p[i].y)) { printf("%I64d %I64d %I64d\n",p[0].id,p[1].id,p[i].id); break; } } } return 0; }
