codeforces 618 C. Constellation

codeforces 618C

C. Constellation

introduction

寻找一个三角形，使得三角形中没有其他点

method

有多种思路，我写三个我看到的

1. 取一个面积不为零的三角形，然后枚举每个点，如果点在三角形内，将三角形其中一个点替换为这个点
2. 将所有点先按x从小到大排序，如果x相等，在按y从小到大排序
3. 任取一个点，找到距离这个点最短的和第二短的点，并且三点不共线

我先开始是按照思路1，失败了，用了思路2

useful knowledge

向量叉乘是一种很有用的操作

• 判断三点共线
• 计算三角形面积

模板

ll area(point &p1,point &p2,point &p3)
{
    ll x1=p2.x-p1.x,y1=p2.y-p1.y;
    ll x2=p3.x-p1.x,y2=p3.y-p1.y;
    return x1*y2-x2*y1;
}

tips

reference

二维平面上判断点是否在三角形内
向量的点乘与叉乘

AC code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
struct point{
    int x,y,id;
    bool operator <(const point &p)const
    {
        return (x<p.x)||(x==p.x&&y<p.y);
    }
};
int n;
point pts[MAXN];
///叉积的作用 判断三点共线||计算三角形面积
ll area(point &p1,point &p2,point &p3)
{
    ll x1=p2.x-p1.x,y1=p2.y-p1.y;
    ll x2=p3.x-p1.x,y2=p3.y-p1.y;
    return x1*y2-x2*y1;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n ;i++ ){
        scanf("%d%d",&pts[i].x,&pts[i].y);
        pts[i].id=i;
    }
    sort(pts+1,pts+1+n);
    int idx;
    for(idx=3;idx<=n ;idx++ ){
        if(area(pts[1],pts[2],pts[idx])!=0)break;
    }
    printf("%d %d %d",pts[1].id,pts[2].id,pts[idx].id);
}