0w1

CFR 618 C. Constellation ( Adhoc )

Problem - C - Codeforces
Take any point first, there will be at least one triangle that does not contain any other points inside, which can be formed with it. In order to avoid points inside the triangle, we can simply take any two points nearest to the chosen first point, that do not all lie on the same line. This can be done with some care with EPS.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXABSXY = 1e9 + 9;

int n;
int x[ MAXN ], y[ MAXN ];

const double EPS = 1e-25;
const double INF = 1e25;

double dis2( int u, int v ){
    double dx = x[ u ] - x[ v ];
    double dy = y[ u ] - y[ v ];
    return dx * dx + dy * dy;
}

double getSlope( int u, int v ){
    double dx = x[ u ] - x[ v ];
    double dy = y[ u ] - y[ v ];
    if( fabs( dx ) < EPS ) return INF;
    return dy / dx;
}

void solve(){
    double near1_dis = INF, near2_dis = INF;
    double near1_slope = -INF, near2_slope = -INF;
    int near1_idx = -1, near2_idx = -1;
    for( int i = 1; i < n; ++i ){
        double d0i = dis2( 0, i );
        double slope = getSlope( 0, i );
        // cout << d0i << " " << slope << endl;
        if( near1_dis > d0i ){
            if( fabs( slope - near1_slope ) > EPS ){
                near2_dis = near1_dis;
                near2_slope = near1_slope;
                near2_idx = near1_idx;
            }
            near1_dis = d0i;
            near1_slope = slope;
            near1_idx = i;
        } else if( near2_dis > d0i ){
            if( fabs( slope - near1_slope ) < EPS )
                continue;
            near2_dis = d0i;
            near2_slope = slope;
            near2_idx = i;
        }
    }
    // cout << near1_slope << " " << near2_slope << endl;
    printf("%d %d %d\n", 1, ++near1_idx, ++near2_idx);
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i )
        scanf("%d%d", x + i, y + i);
    solve();
    return 0;
}