Cod sursa(job #1332667)

Utilizator FlowstaticBejan Irina Flowstatic Data 2 februarie 2015 11:51:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <list>
#include <algorithm>
#include <cmath>
#define Nmax 120005
#define INF 1000000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct
{
    double x,y;
} V[Nmax],fr;

list<punct> li;

void Citire();
double Aria(double x0, double x1, double x2, double y0, double y1, double y2);
int compare(punct a, punct b);
void ParcurgereLista();
int N;
void Afisare();

int main()
{
    Citire();
    sort(V+2,V+N+1,compare);
    ParcurgereLista();
    Afisare();
    return 0;
}

void Citire()
{
    int i;
    fin>>N;

    int poz;
    fr.x = fr.y = INF;
    for(i=1;i<=N;i++)
    {
        fin>>V[i].x>>V[i].y;
        if(V[i].x<fr.x)
            fr=V[i], poz=i;
        else if(V[i].x== fr.x && V[i].y< fr.y)
            fr.y=V[i].y, poz=i;
    }
    swap(fr,V[poz]);
}


int compare(punct a, punct b)
{
    return( Aria(a.x,fr.x,b.x, a.y, fr.y,b.y)>0);
}

double Aria(double x0, double x1, double x2, double y0, double y1, double y2)
{
    return (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
}

void ParcurgereLista()
{

    int i;
    for(i=1;i<=N;i++)
            li.push_back(V[i]);


     list<punct>::iterator it0,it1,it2;
     it0=it1=it2=li.begin();
     it1++; it2++; it2++;

    do
    {
        if(Aria((*it0).x, (*it1).x,(*it2).x,(*it0).y,it1->y,it2->y)<0)
           {
               it0++; it1++; it2++;
           }
        else
            {
                li.erase(it1); it1=it0; it0--;
            }
    }while(it2!=li.end());
}

void Afisare()
{
    fout<<li.size()<<'\n';
    list<punct>::iterator it;
    fout<<fixed;
    for(it=li.begin(); it!=li.end(); ++it)
        fout<<(it->x)<<" "<<(it->y)<<'\n';
}