Cod sursa(job #1337583)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 9 februarie 2015 11:14:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <iomanip>
#define pb push_back
#define NMAX 100
#define infinite 10000000
using namespace std;

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

struct point{
    float x;
    float y;
};


int k;
int s;
point P[NMAX];


bool arecollinear(point A, point B, point C)
{
    return (B.y - A.y)*(C.x-B.x)==(B.x-A.x)*(C.y-B.y);
}
float slope(point A, point B)
{
    if(B.x == A.x)
        return (B.y > A.y) ? infinite: -infinite;
    else
        if(B.y < A.y && B.y < A.y)
            return -(B.y - A.y)/(B.x - A.x);
        else
            return (B.y - A.y)/(B.x - A.x);
}

void getnext(point A){
    int maxslope = slope(A, P[1]);
    int maxi;
    for(int i=1; i<=k; i++)
        if(slope(A, P[i]) > maxslope){
            maxslope = slope(A, P[i]);
            maxi = i;
        }
    if(maxi!=s)
    {
        fout<<P[maxi].x<<" "<<P[maxi].y<<"\n";
        getnext(P[maxi]);
    }
}
int main() {
    fin>>k;
    for(int i=1; i<=k; i++)
        fin>>P[i].x>>P[i].y;
    
    
    int minx = P[1].x;
    for(int i=1; i<=k; i++)
        if(P[i].x<minx)
            minx=P[i].x,
            s = i;
    fout<<setprecision(6)<<fixed<<P[s].x<<" "<<P[s].y<<"\n";
    getnext(P[s]);
    
    return 0;
}