Cod sursa(job #1805320)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 13 noiembrie 2016 17:33:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define x first
#define y second
#define mp make_pair
#define pdd pair<double,double>
#define LE 160666
#include <iomanip>
#define inf 1<<26
#include <algorithm>


namespace geometry{

double determinant(const std::vector<std::vector<double> > &a){
    double result=0;

    result+=a[0][0]*a[1][1]*a[2][2];
    result+=a[1][0]*a[2][1]*a[0][2];
    result+=a[2][0]*a[0][1]*a[1][2];

    result-=a[0][2]*a[1][1]*a[2][0];
    result-=a[1][2]*a[2][1]*a[0][0];
    result-=a[2][2]*a[0][1]*a[1][0];
    return result;
}

class Triangle{
public:
    Triangle(double p1x,double p1y,
                double p2x,double p2y,
                double p3x,double p3y){
        p1.first=p1x;
        p2.first=p2x;
        p3.first=p3x;
        p1.second=p1y;
        p2.second=p2y;
        p3.second=p3y;
    }

    std::pair<double,double> p1,p2,p3;
};


double get_signed_area(Triangle T)  {
        std::vector<std::vector<double> > a(3,std::vector<double>(3,0));
        a[0][0]=a[1][0]=a[2][0]=1;
        a[0][1]=T.p1.first,a[0][2]=T.p1.second;
        a[1][1]=T.p2.first,a[1][2]=T.p2.second;
        a[2][1]=T.p3.first,a[2][2]=T.p3.second;
        return determinant(a);
}
}

 
pdd X[LE],cover[LE];
int i,n,posx,K;
double ymin=inf;
double cross(pdd i1,pdd i2,pdd i3)
{
    return -1;
 //   geometry::Triangle T(i1.x,i1.y,i2.x,i2.y,i3.x,i3.y);
   // return geometry::get_signed_area(T);
}
bool comp(pdd i1,pdd i2)
{
    if (cross (X[n+1],i1,i2)<0)return true;
    return false;
}
 
int main()
{
    f>>n;
    for(i=1; i<=n; ++i) {
        f>>X[i].x>>X[i].y;
        if (X[i].y<ymin) {
            ymin=X[i].y;
            posx=i;
        }
    }
 
    swap(X[posx],X[n]);
    --n;
 
    cover[++K]=X[n+1];
    sort(X+1,X+n+1,comp);
 
    cover[++K]=X[1];
 
    for(i=2;i<=n;++i)
    {
       while (K>1&&cross(cover[K-1],cover[K],X[i])>0)
         --K;
      cover[++K]=X[i];
    }
  g<<fixed;
  g<<setprecision(6);
    g<<K<<'\n';
    for(i=K;i>=1;--i)
      g<<cover[i].x<<" "<<cover[i].y<<'\n';
 
    f.close();
    g.close();
    return 0;
}