Cod sursa(job #1361931)

Utilizator NacuCristianCristian Nacu NacuCristian Data 26 februarie 2015 01:58:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define inf 0x7fffffff
using namespace std;

struct nod
{
    double x,y;
    double m;
    void atr(double a, double b)
    {
        x=a;
        y=b;
    }
}st;

int n;
vector<nod>v;

void citire()
{
    st.atr(inf,inf);
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    double a,b;
    for(int i=0;i<n;i++)
    {
        scanf("%lf %lf",&a,&b);
        nod aux;
        aux.atr(a,b);
        v.push_back(aux);
        if(b<st.y)
        {
            st=aux;
            swap(v[0],v[v.size()-1]);
        }
        else
            if(b==st.y && a>st.x)
            {
               st=aux;
               swap(v[0],v[v.size()-1]);
            }
    }
    for(int i=1;i<n;i++)
        if(v[i].y==st.y)
            v[i].m=-inf;
        else if(v[i].x==st.x)
            v[i].m=0;
        else
            v[i].m=(v[i].y-st.y)/(v[i].x-st.x);

}


bool cmp(nod a, nod b)
{
    if(a.m>0 && b.m>0)
        return a.m<b.m;
    else if(a.m>0 && b.m<=0)
        return true;
    else if(a.m<=0 && b.m>0)
        return false;
    else if(a.m==-inf)
            return a.m>b.m;
    else
        if(a.m<0 && b.m<0)
            return a.m<b.m;
    else
        if(a.m==0 && b.m<0)
            return true;

}


int semndetneg(nod a, nod b, nod c)
{
    if(b.y*(a.x-c.x)+c.y*(b.x-a.x)+a.y*(c.x-b.x)>0)
        return 1;
    return 0;


}

vector <int> sol;

void magie()
{
    sol.push_back(0);
    sol.push_back(1);
    for(int i=2;i<n;i++)
    {
        if(semndetneg(v[sol[sol.size()-2]],v[sol[sol.size()-1]],v[i]))
        {
            sol.push_back(i);
            continue;
        }
        else
        {
            sol.erase(sol.begin()+sol.size()-1,sol.begin()+sol.size());
            i--;
            continue;
        }
    }
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",sol.size());
    for(int i=0;i<sol.size();i++)
        printf("%lf %lf\n",v[sol[i]].x,v[sol[i]].y);

}

int main()
{
    citire();
    sort(v.begin()+1,v.end(),cmp);

    magie();
    return 0;
}