triangoli.cpp

#include <stdio.h>
#include <algorithm>
#include <deque>

using namespace std;

struct Point {
    long double x,y;
//  char c;
};

int func(deque<Point> p){

    int out = 0;

    // cerco il punto che sta più in basso e a parità di y quello più a destra
    int minY = 0;
    for(int i=1; i<p.size(); i++)
        if(p[i].y < p[minY].y || (p[i].y == p[minY].y && p[i].x > p[minY].x))
            minY = i;
//  printf("%c\n\n\n", p[minY].c);

    int ok,ok2;
    double angle;

    // salvo le coordinate del punto
    long double x = p[minY].x, y = p[minY].y;

    // salvo il primo punto
    struct Point primo = p[minY];
    // elimino il primo punto
    p.erase(p.begin()+minY);

    // primo ciclo
    do{
        ok = -1;
        ok2 = -1;

        for(int i=0; i<p.size(); i++)
            if(x != p[i].x){

                double a = (double)(p[i].y-y)/(p[i].x-x);

                if(a>0 && x<p[i].x){
                    if(ok == -1){
                        ok = i;
                        angle = a;
                    }
                    else{
                        if(a < angle){
                            ok = i;
                            angle = a;
                        }
                        else
                            if(a == angle)
                                if(p[i].x > p[ok].x)
                                    ok = i;
                    }
                }
            }
            else{
                if(ok == -1){
                    if(ok2 == -1)
                        ok2 = i;
                    else
                        if(p[ok2].y > p[i].y)
                            ok2 = i;
                }
            }

        if(ok != -1){
            out++;
            x = p[ok].x;
            y = p[ok].y;
//          printf("%c\n", p[ok].c);
            p.erase(p.begin()+ok);
        }
        else
            if(ok2 != -1){
                out++;
                x = p[ok2].x;
                y = p[ok2].y;
//              printf("%c\n", p[ok2].c);
                p.erase(p.begin()+ok2);
            }

    }while(ok != -1);

    // secondo ciclo
    do{
        ok = -1;
        ok2 = -1;

        for(int i=0; i<p.size(); i++)
            if(x != p[i].x)
                if(y != p[i].y){

                    double a = (double)(p[i].y-y)/(p[i].x-x);

                    if(a<0 && x>p[i].x){
                        if(ok == -1){
                            ok = i;
                            angle = a;
                        }
                        else{
                            if(a < angle){
                                ok = i;
                                angle = a;
                            }
                            else
                                if(a == angle)
                                    if(p[i].x < p[ok].x)
                                        ok = i;
                        }
                    }
                }
                else{
                    if(ok == -1){
                        if(ok2 == -1)
                            ok2 = i;
                        else
                            if(p[ok2].x > p[i].x)
                                ok2 = i;
                    }
                }


        if(ok != -1){
            out++;
            x = p[ok].x;
            y = p[ok].y;
//          printf("%c\n", p[ok].c);
            p.erase(p.begin()+ok);
        }
        else
            if(ok2 != -1){
                out++;
                x = p[ok2].x;
                y = p[ok2].y;
//              printf("%c\n", p[ok2].c);
                p.erase(p.begin()+ok2);
            }

    }while(ok != -1);

    // rimetto il primo punto nella lista per poter chiudere il cerchio
    p.push_back(primo);

    // terzo ciclo
    do{
        ok = -1;
        ok2 = -1;

        for(int i=0; i<p.size(); i++)
            if(x != p[i].x){

                double a = (double)(p[i].y-y)/(p[i].x-x);

                if(a>0 && x>p[i].x){
                    if(ok == -1){
                        ok = i;
                        angle = a;
                    }
                    else{
                        if(a < angle){
                            ok = i;
                            angle = a;
                        }
                        else
                            if(a == angle)
                                if(p[i].x < p[ok].x)
                                    ok = i;
                    }
                }
            }
            else{
                if(ok == -1){
                    if(ok2 == -1)
                        ok2 = i;
                    else
                        if(p[ok2].y > p[i].y)
                            ok2 = i;
                }
            }

        if(ok != -1){
            out++;
            x = p[ok].x;
            y = p[ok].y;
//          printf("%c\n", p[ok].c);
            p.erase(p.begin()+ok);
        }
        else
            if(ok2 != -1){
                out++;
                x = p[ok2].x;
                y = p[ok2].y;
//              printf("%c\n", p[ok2].c);
                p.erase(p.begin()+ok2);
            }

    }while(ok != -1);

    // quarto e ultimo ciclo
    do{
        ok = -1;
        ok2 = -1;

        for(int i=0; i<p.size(); i++)
            if(x != p[i].x)
                if(y != p[i].y){

                    double a = (double)(p[i].y-y)/(p[i].x-x);

                    if(a<0 && x<p[i].x){
                        if(ok == -1){
                            ok = i;
                            angle = a;
                        }
                        else{
                            if(a < angle){
                                ok = i;
                                angle = a;
                            }
                            else
                                if(a == angle)
                                    if(p[i].x > p[ok].x)
                                        ok = i;
                        }
                    }
                }
                else{
                    if(ok == -1){
                        if(ok2 == -1)
                            ok2 = i;
                        else
                            if(p[ok2].y > p[i].y)
                                ok2 = i;
                    }
                }

    if(ok != -1){
        out++;
        x = p[ok].x;
        y = p[ok].y;
//      printf("%c\n", p[ok].c);
        p.erase(p.begin()+ok);
    }
    else
        if(ok2 != -1){
            out++;
            x = p[ok2].x;
            y = p[ok2].y;
//          printf("%c\n", p[ok2].c);
            p.erase(p.begin()+ok2);
        }


    }while(ok != -1);

    return out;
}

main(){
    FILE *pF = fopen("input.txt", "r");
    int n;
    fscanf(pF, "%d", &n);
    int i;
    deque<Point> p;
    struct Point x;
    int a,b;
    for(i=0; i<n; i++){
        fscanf(pF, "\n%d %d", &a, &b);
        x.x = (long double)a;
        x.y = (long double)b;
//      x.c = 'a'+i;
        p.push_back(x);
    }
    if(p.size()<4)
        return 123;
    int ris = func(p);
//  printf("%d", ris);
    FILE *pF2 = fopen("output.txt", "w");
    fprintf(pF2, "%d", ris);
    fclose(pF2);
}