Cod sursa(job #1827759)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 12 decembrie 2016 11:53:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <iomanip>

using namespace std;

ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

const int maxn = 120000;

struct puncte{
    float x, y;
};

puncte S_INF[maxn], S_SUP[maxn], P[maxn], SOL[maxn], pmin, pmax, aux;
int n, smin, smax;

float sarrus(float x1, float y1, float x2, float y2, float x3, float y3);
bool cmp(puncte a, puncte b);

int main()
{
    pmin.x=99999999;
    fi>>n;
    for(int i=1;i<=n;i++)
    {
        fi>>aux.x>>aux.y;
        if(aux.x<pmin.x)
            pmin=aux;
        else if(aux.x==pmin.x)
            if(aux.y<pmin.y) pmin=aux;
        if(aux.x>pmax.x)
            pmax=aux;
        else if(aux.x==pmax.x)
            if(aux.y>pmax.y) pmax=aux;
        P[i]=aux;
    }
    S_INF[++smin]=pmin;
    S_INF[++smin]=pmax;
    S_SUP[++smax]=pmin;
    S_SUP[++smax]=pmax;
    for(int i=1;i<=n;i++)
        {
            if((pmin.x!=P[i].x || pmin.y!=P[i].y) && (pmax.x!=P[i].x || pmin.y!=P[i].y))
            {
                if(sarrus(pmin.x,pmin.y,pmax.x,pmax.y,P[i].x,P[i].y)<0)
                    S_INF[++smin] = P[i];
                else S_SUP[++smax] = P[i];
            }
        }

    sort(S_INF+1,S_INF+smin+1,cmp);
    sort(S_SUP+1,S_SUP+smax+1,cmp);
    int i=1;
    while(i+2<smin)
    {
        puncte p1=S_INF[i],p2=S_INF[i+1],p3=S_INF[i+2];
        if(sarrus(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y)>0) i++;
        else
        {
            for(int j=i+1;j<smin;j++)
                S_INF[j] = S_INF[j+1];
            smin--;
        }
    }
    i=1;
     while(i<smax)
    {
        puncte p1=S_SUP[i],p2=S_SUP[i+1],p3=S_SUP[i+2];
        if(sarrus(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y)<0) i++;
        else
        {
            for(int j=i+1;j<smax;j++)
                S_SUP[j] = S_SUP[j+1];
            smax--;
        }
    }
    fo<<smin+smax<<"\n";
    for(i=1;i<=smin;i++)
        fo<<setprecision(12)<<S_INF[i].x<<" "<<setprecision(12)<<S_INF[i].y<<"\n";
    for(i=2;i<=smax;i++)
        fo<<setprecision(12)<<S_SUP[i].x<<" "<<setprecision(12)<<S_SUP[i].y<<"\n";

    return 0;
}

float sarrus(float x1, float y1, float x2, float y2, float x3, float y3)
{
    return (float)(x2*y1+x1*y3+y2*x3-x3*y1-y3*x2-x1*y2);
}


bool cmp(puncte a, puncte b)
{
    if(a.x<b.x)
        return true;
    return false;
}