Cod sursa(job #1074905)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 8 ianuarie 2014 09:37:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=120005;
struct point
{
    double x,y;
};
point p[MAXN];
int n;
void read()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    for (int i=1; i<=n; ++i)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
}
double cross_product(point A, point B, point C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
}
bool cmp(const point& A, const point& B)
{
    return cross_product(p[1],A,B);
}
void solve()
{
    int i,pos=1;
    for (i=2; i<=n; ++i)
    {
        if (p[i].x<p[pos].x)
            pos=i;
        else
        {
            if (p[i].y<p[pos].y)
                pos=i;
        }
    }
    swap(p[pos],p[1]);
    sort(p+2,p+n+1,cmp);


}
void write()
{
    freopen("infasuratoare.out","w",stdout);
    for (int i=1; i<=n; ++i)
    {
        printf("%lf %lf\n",p[i].x,p[i].y);
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}