Cod sursa(job #3219741)

Utilizator DaniMoloMolodet Andrei Daniel DaniMolo Data 1 aprilie 2024 06:31:56
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <math.h>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

int n, nrRele = 0;
double a[10][10];
double x[100], y[100], sir[10];
bool folosit[100], inter[100];

double calc(){
    double p1 = 0, p2 = 0;
    p1 += a[1][1] * a[2][2] * a[3][3] + a[1][2] * a[2][3] * a[3][1] + a[1][3] * a[2][1] * a[3][2];
    p2 += a[3][1] * a[2][2] * a[1][3] + a[3][2] * a[2][3] * a[1][1] + a[3][3] * a[2][1] * a[1][2];

    return p1 - p2;
}

double detMat(int pct[]){
    for(int i = 1; i <= 3; i++){
        a[i][1] = x[pct[i]];
        a[i][2] = y[pct[i]];
        a[i][3] = 1;
    }

    return calc();
}

void citire(){
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> x[i] >> y[i];
}

bool verificare(int v[]){
    bool semn = false;
    int s[] = {0, v[1], v[2], v[4]}, aux;
    aux = detMat(s);
    if(aux == 0)
        return false;
    if(aux > 0)
        semn = true;

    s[1] = v[2];
    s[2] = v[3];
    aux = detMat(s);
    if(aux == 0)
        return false;
    if((aux > 0) != semn)
        return false;

    s[1] = v[3];
    s[2] = v[1];
    aux = detMat(s);
    if(aux == 0)
        return false;
    if((aux > 0) != semn)
        return false;

    return true;
}

void backTrack(int pas){
    if(pas == 5){
        if(verificare(sir)){// pct interior
            inter[sir[4]] = true;
            nrRele++;
        }
        return;
    }

    for(int i = 1; i <= n; i++){
        if(folosit[i])
            continue;
        if(pas == 4)
            if(inter[i])
                continue;
        folosit[i] = true;
        sir[pas] = i;
        backTrack(pas + 1);
        folosit[i] = false;
    }
}

void infasConv(){
    backTrack(1);
}

void afisare(){
    cout << n - nrRele << "\n";
    for(int i = 1; i <= n; i++)
        if(!inter[i])
            cout << x[i] << " " << y[i] << "\n";
}

int main()
{
    citire();

    infasConv();

    afisare();
    return 0;
}