Cod sursa(job #1883139)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 17 februarie 2017 19:10:23
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 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);

    /*for(int i=0;i<n;i++)
        cout<<A[i].first << " "<<A[i].second<<endl;
    cout<<endl;*/
    Q[0]=0;
    for(int i=1;i<n;i++)
        if(k==1)
            Q[k++]=i;
        else
        {
            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;
}