Cod sursa(job #1082516)

Utilizator robert.onesimRobert Onesim robert.onesim Data 14 ianuarie 2014 18:41:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second
FILE *fout;
using namespace std;
ifstream fin("infasuratoare.in");
//ofstream fout("infasuratoare.out");
typedef pair<double, double> Point;
Point v[NMAX];
Point stack[NMAX];
int n;
void read()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
}
double cross_product(Point A, Point B, Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int comp(Point p1, Point p2)
{
    return cross_product(v[1],p1,p2)<0;
}
void sortare()
{
    int pos=1;
    for(int i=2;i<=n;i++)
        if(v[i]<v[pos])
            pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,comp);
}
void solve()
{
    sortare();
    stack[1]=v[1];
    stack[2]=v[2];
    int head=2;
    for(int i=3;i<=n;i++)
    {
        while(head>=2 && cross_product (stack[head-1],stack[head], v[i])>0)
            --head;
        stack[++head]=v[i];
    }
   // fout<<head<<"\n";
   fout=fopen("infasuratoare.out","w");
   fprintf(fout,"%d\n",head);
    for (int i = head; i >= 1; --i)
        fprintf(fout,"%0.6lf %0.6lf\n",stack[i].x,stack[i].y);
        //fout << setprecision(9) << stack[i].x << " " << stack[i].y << "\n";
}
int main()
{
    read();
    solve();
}