Cod sursa(job #871246)

Utilizator costi_.-.Costinnel costi_.-. Data 4 februarie 2013 17:20:53
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<cstdio>
#include<fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120001
using namespace std;

struct punct
{
    double x,y;
};

punct P[nmax],ST[nmax];
int N,M;

bool comp(punct A,punct B)
{
   if(A.x<B.x)
   return true;
   else
      if(A.x==B.x && A.y<B.y)
      return true;
   return false;
}

double delta(punct &p1,punct &p2,punct &p3)
{
    return(
    (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
}



void citeste()
{
    FILE *f=fopen("infasuratoare.in","r");
    int i;

    fscanf(f,"%d",&N);
    for(i=1;i<=N;i++)
    fscanf(f,"%lf %lf",&P[i].x,&P[i].y);

    fclose(f);
}

void rezolva()
{
    int i,t;
    sort(P+1,P+N+1,comp);
    ST[1]=P[1];
    ST[2]=P[2];
    M=2;
    for(i=3;i<=N;i++)
    {
        while(M>=2 && delta(ST[M-1],ST[M],P[i])<=0)
        --M;
        ST[++M]=P[i];
    }

    for(i=N-1;i>=1;i--)
    {
        while(M>=2 && delta(ST[M-1],ST[M],P[i])<=0)
        --M;
        ST[++M]=P[i];
    }
}

void scrie()
{
    ofstream g("infasuratoare.out");
    int i;

    g<<M-1<<'\n';
    g<<fixed;
    g<<setprecision(6);
    for(i=1;i<=M-1;i++)
    g<<ST[i].x<<' '<<ST[i].y<<'\n';

    g.close();
}

void scrie2()
{
    FILE *g=fopen("infasuratoare.out","w");

    fprintf(g,"%d\n",M-1);
    for(int i=1;i<=M-1;i++)
    fprintf(g,"%lf %lf\n",ST[i].x,ST[i].y);

    fclose(g);
}

int main()
{
    citeste();
    rezolva();
    scrie2();
    return 0;
}