Cod sursa(job #2190286)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 martie 2018 13:45:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define DIM 120005
#define x first
#define y second
#define point pair <double,double>

using namespace std;

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

int N,pos;

pair <double,double> P[DIM];

point Stack[DIM];

double trig(point p1,point p2,point p3){
    return (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);
}

int cmp(const point &p1,const point &p2){
    return trig(P[1],p1,p2) > 0;
}

int main(){

    fin >> N;

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

    pos=1;

    for(int i=2;i<=N;i++)
        if(P[i].y < P[pos].y || (P[i].y==P[pos].y && P[i].x < P[pos].y))
            pos=i;

    swap(P[1],P[pos]);

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


    int top=2;
    Stack[1]=P[1];
    Stack[2]=P[2];

    for(int i=3;i<=N;i++){
        while(top>=1 && trig(Stack[top-1],Stack[top],P[i]) < 0)
            top--;
        Stack[++top]=P[i];
    }

    fout << top << "\n";

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

}