Cod sursa(job #1807306)

Utilizator dinu_sergiuDinu Sergiu Andrei dinu_sergiu Data 16 noiembrie 2016 12:32:37
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#define nmax 120001


using namespace std;

FILE *f=fopen("infasuratoare.in", "r");
FILE *g=fopen("infasuratoare.out", "w");

struct point
{
    float x, y;
} p[nmax];

int n;

void Citire()
{
    int i;
    fscanf(f, "%d", &n);
    for(i=1; i<=n; i++)
        fscanf(f, "%f%f", &p[i].x, &p[i].y);
    //n++;
    //p[n].x=p[n].y=0;
}

bool comp(point p1, point p2)
{
    float v1, v2;
    v1=(float) (p1.y-p[1].y)/(p1.x-p[1].x);
    v2=(float) (p2.y-p[1].y)/(p2.x-p[1].x);
    if(v1>v2) return false;  //
    return true;
}

void SortPoints()
{
    int i, poz;
    poz=1;
    for(i=1; i<=n; i++)
        if(p[i].x<p[poz].x)
            poz=i;
        else if(p[poz].x==p[i].x)
                if(p[poz].y<p[i].y)
                    poz=i;
    point aux;
    aux=p[1];
    p[1]=p[poz];
    p[poz]=aux;
    sort(p+2, p+n+1, comp);
}

int sens(point p1, point p2, point p3)
{
    int var, sol;
    var=p1.x*p2.y+p2.x*p3.y+p1.y*p3.x-p3.x*p2.y-p3.y*p1.x-p2.x*p1.y;
    if(var<0) return -1;
    if(var>0) return 1;
    return 0;
}

void CreatePolygon()
{
    int stiva[nmax]={0}, top, it, j, bun, i;
    stiva[1]=1;
    stiva[2]=2;
    top=2; it=3;
    while(stiva[top]!=1)
    {
        top++; stiva[top]=it;
        bun=1;
        for(i=1; i<=n; i++)
            if(sens(p[stiva[top-1]], p[stiva[top]], p[i])<0)
        {
            top--;
            it=i;
            bun=0;
        }
        if(bun)
              it++;
        if(it>n) it=1;

    }
    top--;
    /*
    //daca sunt noduri coliniare in infasuratoarea convexa
    for(i=2; i<top; i++)
        if((p[stiva[i]].x==p[stiva[i-1]].x)&&(p[stiva[i]].x==p[stiva[i+1]].x))
            top--;
    if(p[stiva[top]].x==p[stiva[1]].x&&p[stiva[1]].x==p[stiva[2]].x)
            top--;
    if(p[stiva[top-1]].x==p[stiva[top]].x&&p[stiva[top]].x==p[stiva[1]].x)
            top--;

    for(i=2; i<top; i++)
        if(p[stiva[i]].y==p[stiva[i-1]].y&&p[stiva[i]].y==p[stiva[i+1]].y)
            top--;
    if(p[stiva[top]].y==p[1].y&&p[1].y==p[2].y)
            top--;
    if(p[top-1].y==p[stiva[top]].y&&p[stiva[top]].y==p[1].y)
            top--;
    */
    fprintf(g, "%d\n", top);
    for(i=1; i<=top; i++)
        fprintf(g, "%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
}

int main()
{
    Citire();
    SortPoints();
    CreatePolygon();
    fclose(f);
    fclose(g);
    return 0;
}