Cod sursa(job #1498532)

Utilizator sorynsooSorin Soo sorynsoo Data 8 octombrie 2015 18:44:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 120005
struct pc
{
    double x,y;
}v[MAXN];
vector<pc> sus,jos;
bool cmp(pc A, pc B)
{
    if(A.x==B.x)
        return A.y<B.y;
    return A.x<B.x;
}
int n,i,slim,jlim;
int det(pc A, pc B, pc C)
{
    return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%lf%lf",&v[i].x, &v[i].y);

    sort(v+1,v+n+1,cmp);
    sus.push_back(v[1]); sus.push_back(v[2]); // det sa fie cu minus
    jos.push_back(v[1]); jos.push_back(v[2]); // det sa fie cu plus

    for(i=3; i<=n; i++)
    {
        slim=sus.size();
        while(slim>=2 && det(sus[slim-2],sus[slim-1],v[i]) > 0)
        {
            slim--;
            sus.pop_back();
        }
        sus.push_back(v[i]);

        jlim=jos.size();
        while(jlim>=2 && det(jos[jlim-2],jos[jlim-1],v[i]) < 0)
        {
            jlim--;
            jos.pop_back();
        }
        jos.push_back(v[i]);
    }
    if(jos[0].x==sus[0].x && jos[0].y==sus[0].y)
        jos.erase(jos.begin());

      if(jos[jos.size()-1].x==sus[sus.size()-1].x && jos[jos.size()-1].y==sus[sus.size()-1].y)
        sus.pop_back();

    printf("%d\n",jos.size()+sus.size());
    for(i=0; i<jos.size(); i++)
        printf("%lf %lf\n",jos[i].x,jos[i].y);

    for(i=sus.size(); i>0; i--)
        printf("%lf %lf\n",sus[i].x,sus[i].y);

}