Cod sursa(job #1387413)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 14 martie 2015 09:52:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 100005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
    double x;
    double y;
}P[DIM],first,S[DIM];
int pos,top,N;
double det(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(point p1,point p2){
    return det(first,p1,p2)<0;
}
int main(){
    fin>>N;
    fin>>P[1].x>>P[1].y;
    first=P[1];
    pos=1;
    for(int i=2;i<=N;i++){
        fin>>P[i].x>>P[i].y;
        if(P[i].y<first.y || (P[i].y==first.y && P[i].x<first.x))
            first=P[i],pos=i;
    }
    swap(P[1],P[pos]);
    sort(P+2,P+N+1,cmp);
    S[1]=P[1];
    S[2]=P[2];
    top=2;
    for(int i=3;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<=N;i++)
        fout<<setprecision(6)<<fixed<<S[i].x<<" "<<setprecision(6)<<fixed<<S[i].y<<"\n";
}