Cod sursa(job #1738457)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 6 august 2016 18:56:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
long long N;
typedef struct {double x,y;} POINT;
POINT V[120005],p0;
POINT puncte[120005];
long long i,poz;
POINT st[120005];
long long orient(POINT A,POINT B,POINT C)
{
   long long val=(B.y-A.y)*(C.x-B.x)-(C.y-B.y)*(B.x-A.x);
   if(val<0)
    return -1;
   if(val>0)
    return 1;
    return 0;
}
long long dist(POINT a,POINT b)
{
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
bool comp(POINT a,POINT b)
{
   long long val=orient(p0,a,b);
   if(val==0)
   {
       if(dist(a,p0)>dist(b,p0))
            return 0;
       return 1;

   }
    if(val==-1)
        return 1;
    return 0;
}
void mysort(long long st,long long dr)
{
    long long i=st,j=dr;
    POINT pivot=V[(st+dr)/2];
    while(i<j)
    {
        while(comp(V[i],pivot))
            i++;
        while(!comp(V[j],pivot))
            j--;
        if(i<=j)
        {
            swap(V[i],V[j]);
            i++;
            j--;
        }
    }
    if(i<dr)
        mysort(i,dr);
    if(j>st)
        mysort(st,j);
}
int main()
{
    fscanf(f,"%d",&N);
    poz=1;
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
        if(V[i].y<V[poz].y||(V[i].y==V[poz].y&&V[i].x<V[poz].x))
            poz=i;
    }
    swap(V[1],V[poz]);
    p0=V[1];
    sort(V+2,V+1+N,comp);
  // mysort(2,N);
    puncte[(long long)(++puncte[0].x)]=V[1];
    for(i=2;i<=N;i++)
    {
        while(i<N&&orient(p0,V[i],V[i+1])==0)
            i++;
        puncte[(long long)(++puncte[0].x)]=V[i];
    }
    st[(long long)(++st[0].x)]=puncte[1];
    st[(long long)(++st[0].x)]=puncte[2];
    for(i=3;i<=puncte[0].x;i++)
    {
        while(orient(st[(long long)(st[0].x-1)],st[(long long)(st[0].x)],puncte[i])>=0)
        {
            st[0].x--;
        }
        st[(long long)(++st[0].x)]=puncte[i];
    }
    fprintf(g,"%d\n",(long long)st[0].x);
    for(i=1;i<=st[0].x;i++)
    {
        fprintf(g,"%f %f\n",st[i].x,st[i].y);
    }
    fclose(f);
    fclose(g);
    return 0;
}