Cod sursa(job #1804086)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 12 noiembrie 2016 11:05:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
const int INF = (-1 + (1 << 31));

struct pct {
    double x, y;
} MIN;

vector< pct > V;
vector<int> S;
int N;

void Read();
void Solve();
void Write();
double tg(const pct &a);
bool cmp(const pct &a, const pct &b)  {   return tg(a) > tg(b);   };
bool leftTurn(const pct &a, const pct &b, const pct &c);

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}

void Write() {
    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';
}

void Solve() {
    sort(V.begin(), V.end(), cmp);
    for(int i = 0; i < N; i++) {
        while(S.size() > 1  && leftTurn(V[ S[S.size()-2] ], V[ S[S.size()-1] ], V[i]))
            S.pop_back();
        S.push_back(i);
    }
}

bool leftTurn(const pct &a, const pct &b, const pct &c) {
    int x1, y1, x2, y2;
    x1 = b.x - a.x;
    y1 = b.y - a.y;
    x2 = c.x - a.x;
    y2 = c.y - a.y;
    return x1*y2 > y1*x2;
}

double tg(const pct &a) {
    double x = a.x - MIN.x;
    double y = a.y - MIN.y;
    if(x == 0) {
        if(y == 0)
            return INF;
        return INF - 1;
    }
    return (double)(y / x);
}

void Read() {
    freopen("infasuratoare.in", "rt", stdin);
    freopen("infasuratoare.out", "wt", stdout);
    scanf("%d", &N);
    pct aux;
    V.assign(N, pct());
    MIN.x = MIN.y = INF;
    for(int i = 0; i < N; i++) {
        scanf("%lf %lf", &aux.x, &aux.y);
        V[i] = aux;
        if(aux.x < MIN.x || ( aux.x == MIN.x && aux.y < MIN.y ) )
            MIN = aux;
    }
}