Cod sursa(job #2211521)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 10 iunie 2018 19:20:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#include <algorithm>
#include <bitset>

using namespace std;
FILE *f,*g;

///sens trigonometric=sens antiorar
struct point
{
    double x,y;
}v[120002];
int s[120002];
int n,top;
bitset <120002>yes;

bool how(point &a, point &b)
{
    if(a.x>b.x)
        return (a.x<b.x);
    else
        if(a.x==b.x)
            return (a.y<b.y);
}
void read()
{
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;++i)
        fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,how);
}
///diferenta vectorilor p1p2 si p2p3
///daca e 0 punctele sunt coliniare
///<0 (punctele constituie o orientare in sensul invers acelor de ceasornic),
///>0 (in sensul acelor de ceasornic)
double scanareGhram(point a, point b, point c)
{
    return ((a.x*b.y + b.x*c.y + c.x*a.y) - (b.y*c.x + c.y*a.x + a.y*b.x));
}

void solve()
{
    int ok=1;
    s[++top]=1;
    s[++top]=2,yes[2]=1;
    int i=3;///indicele punctului care urmeaza sa fie verificat pentru a stabili daca se afla pe infasuratoare
    while(!yes[1])///nu s-a realizat cel mai optim poligon
    {
        while(yes[i])
            {
                if(i==n) ok=-1;
                i+=ok;
            }
            while(top>=2 && scanareGhram(v[s[top-1]],v[s[top]],v[i])>0)
                yes[s[top]]=0,--top;
            s[++top]=i,yes[i]=1;
    }
}
void write()
{
    fprintf(g,"%d\n",top-1);
    for(int i=top-1;i>=1;--i)
        fprintf(g,"%lf %lf\n",v[s[i]].x, v[s[i]].y);
}
int main()
{
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    read();
    solve();
    write();
    fclose(f);
    fclose(g);
    return 0;
}