Cod sursa(job #278435)

Utilizator catalina5catalina serban catalina5 Data 12 martie 2009 12:27:50
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include<fstream>
#include<iostream>
#include<math.h>


using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct pct {
    float x,y,d,c;
};
pct s[10000],st[10000],minn;
int n,h;

void citire () {
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>s[i].x>>s[i].y;
    fin.close();
}

float dist (pct a,pct b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int determinant (pct a,pct b,pct c) {
    return (a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-c.y*a.x-a.y*b.x);
}

void minim () {
    minn.x=10000.0,minn.y=10000.0;
    for(int i=0;i<n;i++) {
        if(s[i].y<minn.y)
            minn=s[i];
         else
            if(s[i].y==minn.y)
                if(s[i].x<minn.x)
                    minn=s[i];
    }
}

void afldist () {
    minim();
    for(int i=0;i<n;i++)
        s[i].d=dist(minn,s[i]);
}

void coss () {
    afldist();
    for(int i=0;i<n;i++)
        s[i].c=(float)((minn.x-s[i].x)/(minn.y-s[i].y));
}

void interschimbare () {
    coss();
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++) {
            if(s[i].c>s[j].c) {
                pct aux=s[i];
                s[i]=s[j];
                s[j]=aux;
            }
            else {
                if(s[i].c==s[j].c)
                    if(s[i].d>s[j].d) {
                        pct aux=s[i];
                        s[i]=s[j];
                        s[j]=aux;
            }
        }
}
}

void stergere () {
    for(int i=0;i<n-1;i++) {
        if(s[i].c==s[i+1].c) {
            for(int j=i+2;j<n;j++)
                s[j-1]=s[j];
            n--;
        }
    }
}

void form () {
  //  stergere();
    st[h++]=s[0];
    st[h++]=s[1];
    for(int i=2;i<n;i++)
        if(determinant(st[h-2],st[h-1],s[i])<0)
            st[h++]=s[i];
        else
            st[h-1]=s[i];
}

void afisare () {
    fout<<h<<"\n";
    fout<<st[0].x<<" "<<st[0].y<<"\n";
    for(int i=h-1;i>=1;i--)
        fout<<st[i].x<<" "<<st[i].y<<"\n";
    fout.close();
}

int main () {
    citire();
    interschimbare();
    form();
    afisare();
    return 0;
}