Türkçe

Bu problemin birden fazla çözümü var.

İlk çözümde herhangi bir üçgen seçiyoruz. Sonrasında düzlemdeki diğer noktalar için sırayla şu andaki üçgenimizin içinde mi yoksa dışında mı olduğunu kontrol ediyoruz. Eğer dışındaysa zaten bir problem yaratmayacak, eğer içindeyse de o noktadan ve şu andaki üçgenimizdeki herhangi 2 noktadan oluşan üçgeni yeni üçgenimiz olarak kabul ediyoruz. Bu şekilde en son bulduğumuz üçgenin içinde herhangi bir noktanın olmadığından emin oluyoruz. (Aşağıda verilen örnek kod bu çözümle yazılmıştır.)

Bir diğer çözümdeyse ilk başta herhangi bir nokta seçiyoruz. Sornasında tüm diğer noktaları seçtiğimiz noktaya olan açılarına göre sıralıyoruz. Sonrasında da bu listede ardışık olan 2 noktayı en başta seçtiğimiz nokta ile üçgen oluşturmak için seçiyoruz.

English

There are a couple of solutions for this problem.

The first one is to choose a random triangle. After that, we are going to test every other point if it's inside our triangle or not. If it isn't inside the triangle, then there isn't a problem. But if it's inside it, we should redefine our triangle. We can simply choose 2 points from our existing triangle with the point inside the triangle to construct a new triangle. In the end, we find a triangle that has no points inside it. (The example code is written with this solution in mind.)

For another solution, let's choose an arbitrary point. Then, sort all other points by an angle about this point. After this, we can choose 2 adjacent points from the list. With the first chosen point we construct a triangle.

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll siz = 300005;

ll xx[siz], yy[siz];
ll n, m, k, l;

ll area(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) { 
   return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))); 
} 

bool isInside(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x, ll y) {   
   /* Calculate area of triangle ABC */
   ll A = area (x1, y1, x2, y2, x3, y3); 

   /* Calculate area of triangle PBC */   
   ll A1 = area (x, y, x2, y2, x3, y3); 

   /* Calculate area of triangle PAC */   
   ll A2 = area (x1, y1, x, y, x3, y3); 

   /* Calculate area of triangle PAB */    
   ll A3 = area (x1, y1, x2, y2, x, y); 

   /* Check if sum of A1, A2 and A3 is same as A */ 
   return (A == A1 + A2 + A3); 
} 


ll ccw(ll i, ll j, ll k) {
    ll ax = xx[j]-xx[i], ay = yy[j]-yy[i], bx = xx[k]-xx[i], by = yy[k]-yy[i];
    return ax * by - bx * ay;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>xx[i]>>yy[i];
    }
    int other = -1;
    for(ll i=2;i<n;i++){
        if(ccw(0,1,i)!=0){
            other=i;
            break;
        }
    }
    int a = 0, b = 1, c = other;
    if (ccw(a,b,c) < 0) {int t = b; b = c; c = t;}
    for(int i=2;i<n;i++){
        if(ccw(a,b,i) !=0 && isInside(xx[a], yy[a], xx[b], yy[b], xx[c], yy[c], xx[i], yy[i])) c=i;
        else if(ccw(a,c,i) !=0 && isInside(xx[a], yy[a], xx[b], yy[b], xx[c], yy[c], xx[i], yy[i])) {b=c; c=i;}
    }
    cout<<a+1<<' '<<b+1<<' '<<c+1;

}