Cod sursa(job #1844379)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 9 ianuarie 2017 22:51:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define VAL 120005

using namespace std;

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

struct punct
{
    double x;
    double y;
};

punct P[VAL];
punct sol[VAL];

int N, i, j, M;
int st[VAL], top;
bool ok[VAL];

bool cmp(punct a, punct b)
{
    if (a.x!=b.x)
      return a.x<b.x;
    else
      return a.y<b.y;
}

bool trig(punct a, punct b)
{
    return (a.y / a.x)<(b.y / b.x);
}

double AREA(punct a, punct b, punct c)
{
    double S;
    S=a.x*b.y+b.x*c.y+c.x*a.y;
    S-=a.x*c.y+b.x*a.y+c.x*b.y;
    return S;
}

int main()
{
    fin >> N;
    for (i=1; i<=N; i++)
      fin >> P[i].x >> P[i].y;
    sort(P+1, P+N+1, cmp);
    st[1]=1;
    st[2]=2;
    top=2;
    for (i=3; i<=N; i++)
    {
        while (top!=1 && AREA(P[st[top]], P[st[top-1]], P[i])<0)
          top--;
        st[++top]=i;
    }
    while (top!=0)
      ok[st[top--]]=true;
    st[1]=1;
    st[2]=2;
    top=2;
    for (i=3; i<=N; i++)
    {
        while (top!=1 && AREA(P[st[top]], P[st[top-1]], P[i])>=0)
          top--;
        st[++top]=i;
    }
    while (top!=0)
      ok[st[top--]]=true;
    for (i=1; i<=N; i++)
      if (ok[i]==true)
        sol[++M]=P[i];
    fout << M << '\n';
    sort(sol+1, sol+M+1, trig);
    for (i=1; i<=M; i++)
    {
        fout << fixed << setprecision(12) << sol[i].x << " ";
        fout << fixed << setprecision(12) << sol[i].y << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}