Cod sursa(job #2190285)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 martie 2018 13:43:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 120005

using namespace std;

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

int N, top, origin;

typedef struct point{
    double x, y;
} point;

point P[DIM], S[DIM];

int cadran(point A){

    if(A.x >= 0 && A.y >= 0)
        return 1;
    if(A.x < 0 && A.y >= 0)
        return 2;
    if(A.x < 0 && A.y < 0)
        return 3;
    if(A.x >= 0 && A.y < 0)
        return 4;

}

double det(point A, point B, point C){

    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);

}


int cmp(point A,point B){

    int CadranA = cadran(A);
    int CadranB = cadran(B);

    if(CadranA < CadranB)
        return 1;
    if(CadranA > CadranB)
        return 0;

    return det(P[origin], A, B) > 0;

}

int main(){

    fin >> N;

    fin >> P[0].x >> P[0].y;

    for(int i = 1; i < N ;i ++){
        fin >> P[i].x >> P[i].y;

        if(P[origin].x > P[i].x || (P[origin].x == P[i].x && P[origin].y > P[i].y))
            origin = i;

    }

    swap(P[0], P[origin]);

    sort(P + 1, P + N, cmp);

    S[1] = P[0];
    S[2] = P[1];

    top = 2;

    for(int i = 2; i < N; i ++){

        while(top >= 2 && det(S[top - 1], S[top], P[i]) < 0)
            top --;

        S[++ top] = P[i];

    }

    fout << top << "\n";

    for(int i = 1; i <= top; i ++)
        fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << "\n";

    fin.close();
    fout.close();

    return 0;

}