Cod sursa(job #1738433)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 6 august 2016 18:02:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int N;
typedef struct {double x,y;} POINT;
POINT V[120005],p0;
POINT puncte[120005];
int i,poz;
POINT st[120005];
int orient(POINT A,POINT B,POINT C)
{
   int 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;
}
int 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)
{
   int 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(int st,int dr)
{
    int i,j;
    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+1,V+1+N,comp);
    puncte[(int)(++puncte[0].x)]=V[1];
    for(i=2;i<=N;i++)
    {
        while(i<N&&orient(p0,V[i],V[i+1])==0)
            i++;
        puncte[(int)(++puncte[0].x)]=V[i];
    }
    st[(int)(++st[0].x)]=puncte[1];
    st[(int)(++st[0].x)]=puncte[2];
    st[(int)(++st[0].x)]=puncte[3];
    for(i=4;i<=puncte[0].x;i++)
    {
        while(orient(st[(int)(st[0].x-1)],st[(int)(st[0].x)],puncte[i])>=0)
        {
            st[0].x--;
        }
        st[(int)(++st[0].x)]=puncte[i];
    }
    fprintf(g,"%d\n",(int)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;
}