Cod sursa(job #1892231)

Utilizator markyDaniel marky Data 24 februarie 2017 20:25:25
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int nmax = 120005;

struct Point{
double x,y;
}points[nmax];

int orientation(Point p, Point q, Point r){
double val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);

if(val==0)return 0;

return (val > 0)? 1 : 2;
}

void convexHull(Point points[], int n){
    int i;

vector<Point>hull;

int l=0;
for(i=1;i<n;i++)
    if(points[i].x<points[l].x)l=i;


int p=l,q;

do
{
    hull.push_back(points[p]);

    q=(p+1)%n;

    for(i=0;i<n;i++)
        if(orientation(points[p],points[i],points[q])==2)q=i;

    p=q;

}while(p!=l);
g<<hull.size()<<'\n';
for(i=0;i<hull.size();i++)
    g<<setprecision(12)<<hull[i].x<<" "<<hull[i].y<<'\n';

}


int main()
{
    int n,i;
    f >> n;
    for(i=0;i<n;i++)
        f>>points[i].x>>points[i].y;

    g<<fixed;
    convexHull(points,n);

    return 0;
}