Cod sursa(job #1923180)

Utilizator alexutzualex alex alexutzu Data 10 martie 2017 21:15:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#define NMAX 120001
#define inf 1000000001
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()
{
    FILE *f=fopen("infasuratoare.in","r");
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
    {
         fscanf(f,"%lf%lf",&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);
}
 //A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-B.x*A.y;
 //(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];
    }
    FILE *f1=fopen("infasuratoare.out","w");
    fprintf(f1,"%d\n",u);
    for(int i=1;i<=u;i++)
        fprintf(f1,"%lf %lf\n",REZ[i].x,REZ[i].y);
}

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