Cod sursa(job #1686915)

Utilizator rares00Foica Rares rares00 Data 12 aprilie 2016 15:16:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.55 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <stdio.h>
using namespace std;
//ifstream in("date.in");
//ofstream out("date.out");
FILE * in=fopen("infasuratoare.in","r");
FILE * out=fopen("infasuratoare.out","w");

int np,npaux,vf;
struct pct{
    double x,y;
}p[120001],paux[120001],aux,st[120001];

void citeste()
{
    /*in>>np;
    for(int i=0;i<np;++i)
        in>>p[i].x>>p[i].y;
        */
    fscanf(in,"%d",&np);
    for(int i=0;i<np;++i)
        fscanf(in,"%lf %lf",&p[i].x,&p[i].y);
}
double crossprod(struct pct p1,struct pct p2,struct pct p0)
{
    double t=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
    return t;
}
void quicksort(int st,int dr)
{
    int i=st,j=dr;
    int mij=st;
    do{
        while(i<dr && crossprod(p[mij],p[i],p[0])<0) ++i;
        while(j>st && crossprod(p[mij],p[j],p[0])>0) --j;
        if(i<=j)
        {
            aux=p[i],p[i]=p[j],p[j]=aux;
            ++i,--j;
        }
    }while(i<=j);
    if(i<dr) quicksort(i,dr);
    if(j>st) quicksort(st,j);
}
double laStanga(pct p1,pct p2,pct p3)
{
    double t=(p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);
    if(t<0)
        return 1;
    return 0;
}
double dist(pct p1,pct p2)
{
    double d=sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
    return d;
}
int main()
{
    citeste();

    //Primul Pas
    //: determin p0 cu coordonata verticala cea mai mica
    //: daca exista identitate, se alege cel cu coordonata orizontala cea mai mica
    for(int i=1;i<np;++i)
    {
        if(p[i].y<p[0].y)
            aux=p[i],p[i]=p[0],p[0]=aux;

        else if(p[i].y==p[0].y)
            if(p[i].x<p[0].x)
                aux=p[i],p[i]=p[0],p[0]=aux;
    }

    //Al Doilea Pas
    //: sortez celelalte varfuri in ordinea unghiurilor polare in jurul varfului p0
    /*out<<"Initial:\n";
    for(int i=0;i<np;++i)
        out<<p[i].x<<" "<<p[i].y<<"\n";*/

    quicksort(1,np-1);

    /*out<<"\nDupa sortare:\n";
    struct pct px;
    px.x=5, px.y=0;
    for(int i=0;i<np;++i)
        out<<p[i].x<<" "<<p[i].y<<" "<<crossprod(p[i],px,p[0])<<"\n";
    out<<crossprod(p[5],p[6],p[0])<<"\n";*/
    //: pastrez (in vector aux) numai varfurile de pe aceeasi linie la distanta maxima de p0

    paux[0]=p[0];
    paux[++npaux]=p[1];
    for(int i=2;i<np;++i)
    {
        paux[++npaux]=p[i];
        //daca avem coliniaritate
        //copiem numai punctul de distanta maxima
        if(crossprod(paux[npaux-1],paux[npaux],p[0])==0)
        {
            //daca paux[i] mai departat ca paux[i-1]
            if(dist(paux[npaux],p[0])>dist(paux[npaux-1],p[0]))
                paux[npaux-1]=paux[npaux],--npaux;
            else
                --npaux;
        }
    }
    for(int i=1;i<=npaux;++i)
        p[i]=paux[i];
    np=npaux;

    /*out<<"\nDupa eliminari:\n";
    for(int i=0;i<=np;++i)
        out<<p[i].x<<" "<<p[i].y<<"\n";*/

    //Al Treilea Pas
    //: inserez in STIVA p0,p1,p2
    st[0]=p[0];
    st[1]=p[1];
    st[2]=p[2];
    vf=2;

    //Al Patrulea Pas
    //: pentru fiecare punct, verific daca segmentul format respecta convexitatea poligonului
    for(int i=3;i<=np;++i)
    {
        st[++vf]=p[i];
        while(vf>2 && laStanga(st[vf-2],st[vf-1],st[vf])==0)
            --vf,st[vf]=st[vf+1];
    }

    /*out<<"\nIn stiva:\n";*/
    //out.precision(6);
    fprintf(out,"%d\n",vf+1);
    for(int i=0;i<=vf;++i)
        //out<<st[i].x<<" "<<st[i].y<<"\n";
        fprintf(out,"%.6lf %.6lf\n",st[i].x,st[i].y);
    return 0;
}