Cod sursa(job #1154730)

Utilizator maribMarilena Bescuca marib Data 26 martie 2014 12:53:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct Point
{
   double x, y;
};

Point v[120001], st[120001];
double p1, p2;
int n, i, min1, sf;

bool cmp(const Point A, const Point B)
{
    p1=(A.y-v[0].y)/(A.x-v[0].x);
    p2=(B.y-v[0].y)/(B.x-v[0].x);
    if(A.x==v[0].x)
        {
            p1=10000;
            if(A.y==v[0].y) p1=10001;
        }
    if(B.x==v[0].x)
        {
            p2=10000;
            if(B.y==v[0].y) p2=10001;
        }
    return p1>p2;
}

double tri(Point a, Point b, Point c)
    {
        return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
    }


int main()
{
    ifstream in ("infasuratoare.in");
    ofstream out ("infasuratoare.out");
    in>>n;
    v[0].x=100000;
    for(i=1; i<=n; ++i)
        {
            in>>v[i].x>>v[i].y;
            if(v[i].x<v[0].x)
                {
                    v[0].x=v[i].x;
                    v[0].y=v[i].y;
                    min1=i;
                }
            if(fabs(v[i].x-v[0].x)<=0.00000001)
                {
                    if(v[0].y>v[i].y)
                        {
                            v[0].y=v[i].y;
                            min1=i;
                        }

                }
        }
    sort(v+1, v+n+1, cmp);
    sf=2;
    st[1]=v[1];
    st[2]=v[2];
    for(i=3; i<=n; ++i)
        {
                  while(tri(st[sf], st[sf-1], v[i])<=0&&sf>=2)
                        {
                            sf--;
                        }
                    if(sf==1)
                        {
                            sf++; goto p;
                        }
                    sf++;
                    st[sf]=v[i];
            p: ;
        }
    out<<sf<<"\n";
    out<<setprecision(6)<<fixed;
    out<<st[1].x<<" "<<st[1].y<<"\n";
    for(i=sf; i>=2; --i)
        {
            out<<setprecision(6)<<fixed;
            out<<st[i].x<<" "<<st[i].y<<"\n";
        }
    in.close();
    out.close();
    return 0;
}