Cod sursa(job #1648374)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 11 martie 2016 09:48:58
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <utility>

#define INF ((1<<31)-1)
#define x first
#define y second
using namespace std;

int N;
vector < pair < double, double > > V;
vector < int > S;
pair < double, double > mini;

void citire();
bool cmp(const pair<double, double> &a, const pair<double, double> &b);
double tg (const pair<double, double> &a);
void infasuratoare();
double leftTurn(const pair<double, double> &p1, const pair<double, double> &p2, const pair<double, double> &p3);
void afisare();

int main()
{
    citire();
    sort(V.begin(), V.end(), cmp);
    infasuratoare();
    afisare();
    return 0;
}
void afisare() {
    cout<<S.size()<<'\n';
    for(int i=S.size()-1; i>=0; --i) {
        cout<<fixed<<setprecision(6)<<V[S[i]].x<<' '<<V[S[i]].y<<'\n';
    }
}

double leftTurn(const pair<double, double> &p1, const pair<double, double> &p2, const pair<double, double> &p3) {
    return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
}

void infasuratoare()
{
    for(int i=0; i<N; ++i) {
        if(S.size() > 1 && leftTurn( V[ S[S.size()-2] ], V[ S[S.size()-1] ], V[i] ) > 0 )
            S.pop_back();
        S.push_back(i);
    }
}

double tg (const pair<double, double> &a) {
    double xx, yy;
    xx = a.x - mini.x;
    yy = a.y - mini.y;
    if(xx == 0) {
        if(yy == 0)
            return INF;
        return INF-1;
    }
    return yy/xx;
}

bool cmp(const pair<double, double> &a, const pair<double, double> &b) {
    return tg(a) > tg(b);
}

void citire()
{
    freopen("infasuratoare.in", "rt", stdin);
    freopen("infasuratoare.out", "wt", stdout);
    scanf("%d", &N);
    double a, b;
    mini.x = mini.y = INF;
    for(int i=1; i<=N; ++i) {
        scanf("%lf%lf", &a, &b);
        if(a < mini.x || (a == mini.x || b < mini.y) )
            mini = make_pair(a, b);
        V.push_back( make_pair(a, b) );
    }
}