Cod sursa(job #382249)

Utilizator mihainexMihai Nechita mihainex Data 13 ianuarie 2010 10:21:29
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include<fstream>
#include<iostream>
using namespace std;

struct punct{
    double x;
    double y;
            };    
int n,npf;
punct v[100],pf[100];


void citire();
void qsort(int st,int dr);
int panta(punct a,punct b);
int directie(punct a,punct b,punct c);
void solve();

int main()
{
    citire();
    ofstream fout("infasuratoare.out");
    punct a=v[1];
    int p=1;
    for(int i=2;i<=n;i++)
        if(v[i].x<a.x)
            a=v[i],p=i;
        else
           if(v[i].x==a.x&&v[i].y<a.y)
              a=v[i],p=i;
    pf[++npf]=a;
    for(int i=p;i<n;i++)
        v[i]=v[i+1];
    n--;
    qsort(1,n);
    pf[++npf]=v[1];
    solve();
    fout<<npf<<endl;
    for(int i=2;i<=npf;i++)
      fout<<pf[i].x<<" "<<pf[i].y<<endl;
    fout<<pf[1].x<<" "<<pf[1].y;
    return 0;
}

void citire()
{
    ifstream fin("infasuratoare.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
}

void qsort(int st,int dr)
{
    if(st<dr)
    {
        int i=st,j=dr,d=0;
        punct aux;
        while(i<j)
        {
            if(panta(v[i],v[j])>0)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
                d=1-d;
            }
            i+=d;
            j-=1-d;
      }
      qsort(st,i-1);
      qsort(i+1,dr);
    }
}            

int directie(punct a,punct b,punct c)
{
    double d=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    if(d==0)
        return 0;
    if(d>0)
        return 1;
    return -1;
}

int panta(punct a,punct b)
{
    if(((a.y-pf[1].y)*(b.x-pf[1].x))>=((a.x-pf[1].x)*(b.y-pf[1].y)))
        return 1;
    else
        return 0;
}

void solve()
{
    int gata=0;
    for(int i=2;i<=n&&gata==0;i++)
    {
        double d=directie(pf[npf-1],pf[npf],v[i]);
        if(d<0)
           pf[npf]=v[i];
        if(d>0)
           pf[++npf]=v[i];
        if(v[i].x==pf[1].x&&v[i].y==pf[1].y)
            gata=1;
   }
}