Cod sursa(job #1918415)

Utilizator alexutzualex alex alexutzu Data 9 martie 2017 15:20:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>>
#define NMAX 120001
#define inf 1000000000
using namespace std;
int N;
struct point {double x,y;} P[NMAX],REZ[NMAX];
double xmin=inf,ymin=inf;int imin,p=1,u=1;
void citire()
{
    ifstream fin("infasuratoare.in");
    fin>>N;
    for(int i=1;i<=N;i++)
    {
        fin>>P[i].x>>P[i].y;
        if(P[i].x<xmin)
        {
            xmin=P[i].x;
            ymin=P[i].y;
            imin=i;
        }
        else
        if(xmin==P[i].x&&ymin>P[i].y)
        {
            xmin=P[i].x;
            ymin=P[i].y;
            imin=i;
        }
    }
}

double det(point A,point B,point C)
{
    return (A.x-B.x)*(C.y-B.y)-(A.y-B.y)*(C.x-B.x);
}


int cmp(point A,point B)
{
    return det(P[1],A,B)<0;
}

void rez()
{
    swap(P[1],P[imin]);
    sort(P+2,P+N+1,cmp);
    REZ[1]=P[1];
    REZ[2]=P[2];
    u=2;
    for(int i=3;i<=N;i++)
    {
        while((det(REZ[u-1],REZ[u],P[i])>0)&&u>2)
        u--;
        REZ[++u]=P[i];
    }
    ofstream fout("infasuratoare.out");
    fout<<u<<endl;
    for(int i=p;i<=u;i++)
        fout<<REZ[i].x<<" "<<REZ[i].y<<endl;
}

int main()
{
    citire();
    rez();
    return 0;
}