Cod sursa(job #1883109)

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

int n,sel,k,l_s;
vector <pair <float, float> > A;
vector <int> Q;
float x,y;

void pus(int val)
{
    if(k==l_s)
        Q.push_back(val),k++,l_s++;
    else Q[k++]=val;
}

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(),A.end(),srt);

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