Cod sursa(job #1883147)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 17 februarie 2017 19:13:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define cout cerr
#define MAX 120001
using namespace std;

int n,sel,k=1,l_s;
vector <pair <float, float> > A;
int Q[MAX];
float x,y;

float determinant(pair <float, float> a, pair<float, float> b,pair <float, float> c)
{
    float xa,ya,xb,yb,xc,yc;
    xa=a.first;
    ya=a.second;
    xb=b.first;
    yb=b.second;
    xc=c.first;
    yc=c.second;
    return (xb-xa)*(yc-ya)-(xc-xa)*(yb-ya);
}

bool srt(pair <float, float> a, pair<float, float> b)
{
    return (determinant(A[0],a,b) > 0);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    sel = 0;
    for(int i=0; i<n; i++)
    {
        scanf("%f %f",&x,&y);
        A.push_back(make_pair(x,y));
        if(x<A[sel].first)
            sel=i;
        else if(x==A[sel].first)
            if(y<A[sel].second)
                sel=i;
    }

    if(sel!=0)
    {
        pair <float, float> aux;
        aux = A[0];
        A[0]=A[sel];
        A[sel]=aux;
    }

    sort(A.begin()+1,A.end(),srt);

    k=1;
    Q[0]=0;
    for(int i=1; i<n; i++)
    {
        if(k==1)
            while(determinant(A[Q[k-2]],A[Q[k-1]],A[i])<0 && k>1)
                k--;
        Q[k++]=i;
    }

    printf("%d\n",k);
    for(int i=0; i<k; i++)
        printf("%f %f\n",A[Q[i]].first,A[Q[i]].second);
    return 0;
}