Cod sursa(job #1221691)

Utilizator TibixbAndrei Tiberiu Tibixb Data 21 august 2014 11:14:52
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<vector>
#include<utility>
#include<iomanip>
#include<algorithm>
#define INF 999999999
using namespace std;
pair<double, double> v0, aux;
int n, i, poz, k;
double x, y;
int det(pair<double, double> v1, pair<double, double>v2, pair<double, double>v3){
    return (v2.first-v1.first)*(v3.second-v1.second)-(v3.first-v1.first)*(v2.second-v1.second);
}
int cmp(pair<double, double>v1, pair<double, double>v2){
    return det(v0, v1, v2)>=0;
}
vector<pair <double, double> > v;
pair<double, double> s[120007];

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int main(){
    in>>n;
    v0.first=INF;
    for(i=1; i<=n; i++){
        in>>x>>y;
        v.push_back(make_pair(x, y));
        if(v[i-1]<v0){
            v0=v[i-1];
            poz=i-1;
        }
    }
    aux=v[poz];
    v[poz]=v[0];
    v[0]=aux;
    sort(v.begin()+1, v.end(), cmp);
    s[0]=v[0];
    s[1]=v[1];
    k=1;
    for(i=2; i<n; i++){
        while(det(s[k-1], s[k], v[i])<=0 && k>=1){
            k--;
        }
        s[++k]=v[i];
    }
    out<<k+1<<"\n";
    for(i=0; i<=k; i++)
        out<<fixed<<setprecision(6)<<s[i].first<<" "<<s[i].second<<"\n";
    //for(i=0; i<v.size(); i++)
        //out<<v[i].first<<" "<<v[i].second<<"\n";

return 0;
}