Cod sursa(job #1920842)

Utilizator valentin50517Vozian Valentin valentin50517 Data 10 martie 2017 10:21:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double,double> pdd;
pdd V[120100],St[120100];
double cww(pdd a,pdd b,pdd c){return (b.x -a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);}
bool cmp(pdd a,pdd b){return cww(V[1],a,b) < 0;}
int st,N,poz=1;
int main(){
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin >> N;
    for(int i = 1;i<=N;i++){
        cin >> V[i].x >> V[i].y;
        if(V[i] < V[poz]) poz = i;
    }
    swap(V[1],V[poz]);
    sort(V+2,V+N+1,cmp);
    St[1] = V[1];
    St[2] = V[2];
    st = 2;
    for(int i = 3;i<=N;++i){
        while(st >= 2 && cww(St[st-1],St[st],V[i]) > 0) --st;
        St[++st] = V[i];
    }
    cout <<  st << fixed << setprecision(9) << '\n';
    while(st>0) {cout << St[st].x << ' ' << St[st].y << '\n';--st;}
}