Cod sursa(job #2158179)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 10 martie 2018 11:09:59
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define nmax 120000

using namespace std;

struct pct{
    double x,y;
};

pct v[nmax];
pct st[nmax];
pct dr[nmax];
pct oks[nmax];
pct okd[nmax];

int dir(pct a, pct b, pct c){  // -1 - dreapta, 1 - stanga, 0 - pe dreapta
    double s;
    s=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
    if(s>0)
        s=1;
    if(s<0)
        s=-1;
    int sol=s;
    return sol;
}

int cmp(pct a, pct b){
    if(a.y<b.y)
        return 1;
    else if(a.y==b.y && a.x<b.x)
        return 1;
    return 0;
}

int infas(pct v[], pct ok[], int n, int semn){
    int i=2,k=2;
    ok[0]=v[0];
    ok[1]=v[1];
    while(i<n){
        while(k>1 && dir(ok[k-2],ok[k-1],v[i])*semn>0)
            k--;
        ok[k]=v[i];
        k++;
        i++;
    }
    return k;
}

int main()
{
    FILE *fin, *fout;
    int n,i,poz,k1,k2;
    fin=fopen("infasuratoare.in","r");
    fout=fopen("infasuratoare.out","w");
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++){
        fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
    }
    sort(v,v+n,cmp);
    k1=k2=1;
    st[0]=v[0];
    dr[0]=v[0];
    for(i=1;i<n;i++){
        if(v[i].x<=v[0].x){
            st[k1]=v[i];
            k1++;
        }else{
            dr[k2]=v[i];
            k2++;
        }
    }
    k1=infas(st,oks,k1,1);
    k2=infas(dr,okd,k2,-1);
    fprintf(fout,"%d\n",k1+k2-1);
    for(i=0;i<k2;i++){
        fprintf(fout,"%lf %lf\n",okd[i].x,okd[i].y);
    }
    for(i=k1-1;i>0;i--){
        fprintf(fout,"%lf %lf\n",oks[i].x,oks[i].y);
    }
    return 0;
}