Cod sursa(job #1802356)

Utilizator MaraaMMihali Mara MaraaM Data 10 noiembrie 2016 10:17:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define NMax 120005
struct Point
{
    double x, y;
} v[NMax],s[NMax];
int n,vf;
double cross_product(Point A, Point B, Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);

}
bool compare(Point x, Point y)
{
    return cross_product(v[1],x,y)  <0;
}
int main()
{
    f>>n;
     int poz=0;
    v[poz].x=INT_MAX;
    v[poz].y=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
        if(v[poz].x==v[i].x&&v[poz].y>v[i].y)
            poz=i;
        else if(v[poz].x>v[i].x) poz=i;
    }
    swap(v[poz],v[1]);
    sort(v+2,v+n+1,compare);
    vf=1;
    s[vf]=v[1];
    s[++vf]=v[2];
    for(int i=3;i<=n;++i)
       {

       while(vf>=2&&(cross_product(s[vf-1],s[vf],v[i])>0))
              --vf;
    s[++vf]=v[i]; }
      g<<vf<<'\n';
      for(int i=vf;i>0;--i)
            g<<fixed<<setprecision(6)<<s[i].x<<' '<<s[i].y<<'\n';

    return 0;
}