Cod sursa(job #1629700)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 4 martie 2016 17:49:11
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <utility>//pair
#include <algorithm>
#include <assert.h>
#include <iomanip>
#define Inf (1<<31)-1

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

vector<pair<float,float> > v;
vector< pair<pair<float,float>, float> > nv;
pair<float,float> mini;
stack<int> S;
int n;

float abs(float x)
{
    return (x<0? -x: x);
}


float tg(pair<float,float> a)
{
    float x,y;
    x=(a.first - mini.first);
    y=(a.second - mini.second);
    if(x==0) {
        if (y == 0)
            return Inf;
        else
            return Inf-1;
    }
    return y/x;
}

int cmp(pair<float,float> a, pair<float,float> b) {
 float tg1, tg2;
 tg1 = tg(a);
 tg2 = tg(b);
 return tg1 > tg2;

}

void citire()
{
    int i;
    float d1,d2;//

    fin>>n;
    mini.second=Inf;//
    mini.first=Inf;//
    for(i=1; i<=n; i++)
    {
        fin>>d1>>d2;//depanarea nu trece de citire
        if(d1<mini.first || (d1 == mini.first && d2 < mini.second))                          //luam cel mai din stanga punct si face tg adica y/x adica panta.
            mini=make_pair(d1,d2);
        v.push_back(make_pair(d1,d2));
    }
}

int left_turn(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3)
{
    return (p1.first*p2.second)-(p2.second*p3.first)+(p2.first*p3.second)-(p2.first*p1.second)+(p1.second*p3.first)-(p3.second*p1.first);

}

int main()
{
   // freopen("infasuratoare.in","rt",stdin);
    freopen("infasuratoare.out","wt",stdout);
    citire();
    sort(v.begin(),v.end(),cmp);

    //assert (leftTurn (make_pair (1, 1), make_pair (2, 2), 3) == 1);

    S.push(0);

    for(int i=1; i<n; i++)
    {
        int emij=S.top();
        S.pop();
        while(S.size() && left_turn(v[S.top()],v[emij],v[i])>0){//>0
            emij=S.top();
            S.pop ();
        }
        S.push(emij);
        S.push (i);
    }

    int sz = S.size ();
    cout<<sz<<'\n';
    while(S.size())
    {
        int emij=S.top();
            S.pop ();
        //printf ("%.2lf %.2lf\n", v[emij].first, v[emij].second);
        cout<<fixed<<setprecision(6)<<v[emij].first<<' '<<v[emij].second<<'\n';
    }



    return 0;
}