Cod sursa(job #1361722)

Utilizator dianaa21Diana Pislaru dianaa21 Data 25 februarie 2015 23:16:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#define point pair<double,double>
#define nmax 120002
#define eps 0.000001
using namespace std;
ifstream is ("infasuratoare.in");
ofstream os ("infasuratoare.out");

point V[nmax];
int S[nmax];
struct Comp{
    bool operator()(const point& B, const point& C) {
        return (B.first - V[1].first) * (C.second - V[1].second) -
               (B.second - V[1].second) * (C.first - V[1].first) > 0;
    }
};
int N, poz1;
void Read();
bool Cmp(int,int,int);

int main()
{
    Read();
    V[0].second = 1000000000;
    for(int i = 1; i <= N; ++i)
    {
        if(V[i].first == V[poz1].first)
            if(V[i].first < V[poz1].first)
                poz1 = i;
        if(V[i].second < V[poz1].second)
            poz1 = i;
    }

    swap(V[1], V[poz1]);
    sort(V+2, V+N+1, Comp());

    S[1] = 1;
    S[2] = 2;

    int top = 2;
    for(int i = 3; i <= N; ++i)
    {
        while(top >= 2 && Cmp(S[top-1], S[top], i))
            top--;
        S[++top] = i;
    }
    os << top << "\n";
    for(int i = 1; i <= top; ++i)
        os << fixed << setprecision(6) << V[S[i]].first << " " << V[S[i]].second << "\n";

    is.close();
    os.close();
    return 0;
}
void Read()
{
    double x, y;
    is >> N;
    for(int i = 1; i <= N; ++i)
        is >> V[i].first >> V[i].second;
}
bool Cmp(int a,int b,int c)
{
    point A = V[a];
    point B = V[b];
    point C = V[c];
    return (B.first - A.first) * (C.second - A.second) -
               (B.second - A.second) * (C.first - A.first) < 0;
}