Cod sursa(job #679786)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 13 februarie 2012 18:59:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NM 120010
#define INF 200000000
#define type double

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct poz{type x,y;} V[NM];
int N,i,IND[NM],ST=0;
bool comp(int a,int b) {
    type v1,v2;
    v1=(V[IND[a]].y-V[IND[1]].y)*(V[IND[b]].x-V[IND[1]].x);
    v2=(V[IND[b]].y-V[IND[1]].y)*(V[IND[a]].x-V[IND[1]].x);
    return v1<v2;
}
int SK[NM],k=0;
bool right(int a,int b,int c) {
    return ((V[a].x*V[b].y+V[a].y*V[c].x+V[b].x*V[c].y-V[b].y*V[c].x-V[a].x*V[c].y-V[a].y*V[b].x)<0);
}
int main () {
    f >> N;V[0].x=V[0].y=INF;
    for (i=1;i<=N;i++) {
        f >> V[i].x >> V[i].y;
        IND[i]=i;
        if (V[i].y<V[IND[ST]].y || (V[i].y==V[IND[ST]].y && V[i].x<V[IND[ST]].x)) ST=i;
    }
    swap(IND[1],IND[ST]);
    sort(IND+2,IND+N+1,comp);
    SK[1]=IND[1];SK[2]=IND[2];k=2;
    for (i=3;i<=N;i++) {
        while(right(SK[k-1],SK[k],IND[i]))
            k--;
        SK[++k]=IND[i];
    }
    g << k << '\n';
    g << fixed;
    for (i=1;i<=k;i++) g << setprecision(7) << V[IND[SK[i]]].x << ' ' << V[IND[SK[i]]].y << '\n';
    f.close();g.close();
    return 0;
}