Cod sursa(job #2154455)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 6 martie 2018 22:54:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct punct
{
    double x,y;
};

punct v[120010];
vector<punct> q;

double det(punct p1,punct p2,punct p3)
{
    return (p1.x-p2.x)*(p1.y-p3.y)-(p1.x-p3.x)*(p1.y-p2.y);
}

int cmp(punct a,punct b)
{
    return det(v[1],a,b)>0;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
    for(int i=2;i<=n;i++)
        if(v[i].x<v[1].x) swap(v[i],v[1]);
    sort(v+2,v+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])<0) q.pop_back();
        q.push_back(v[i]);
    }
    printf("%d\n",q.size());
    for(int i=0;i<q.size();i++) printf("%.12f %.12f\n",q[i].x,q[i].y);
    return 0;
}