Cod sursa(job #2355978)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 26 februarie 2019 13:44:52
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
int P;
struct PCT
{
    double x,y;
};
PCT lst[120010];
int N;
int st[120010],added[120010];
bool Critery(PCT A,PCT B)
{
    if(A.y!=B.y) return (A.y<B.y);
    return (A.x<B.x);
}
void Read()
{
    int I;
    fscanf(f,"%d",&N);
    for(I=1;I<=N;++I)
        fscanf(f,"%lf %lf",&lst[I].x,&lst[I].y);
    sort(lst+1,lst+1+N,Critery);
}
struct Puncte
{
    double x,y;
};
Puncte A,B,C;
int Pozitionare(int p1,int p2,int p3)///dacă determinantul este negativ, punctele sunt puse în ordine trigonometrică
{
    double det;
    A.x=lst[p1].x;A.y=lst[p1].y;
    B.x=lst[p2].x;B.y=lst[p2].y;
    C.x=lst[p3].x;C.y=lst[p3].y;
    det=(A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-C.y*A.x-A.y*B.x);
    return det;
}
int nr;
void Solve()
{
    int I=3,unitate=1;
    st[1]=1,st[2]=2;added[2]=1;
    nr=2;
    while(!added[1])///atâta timp cât nu m-am întors înapoi la primul element
    {
        while(added[I])///caut un nou punct și încerc să-l dadaug în înfășurătoare
        {
            if(I==N)unitate=-1;///am ajuns în vârf, deci mă întorc
            I+=unitate;
        }
        while(nr>=2&&Pozitionare(st[nr],st[nr-1],I)>0)///elimin punctele care nu respectă ordinea trigonometrică
            added[st[nr--]]=0;
        st[++nr]=I;added[I]=1;
    }
}
void Displaying()
{
    int i;
    fprintf(g,"%d\n",nr-1);
    for(i=1;i<=nr-1;++i)
        fprintf(g,"%lf %lf\n",lst[st[i]].x,lst[st[i]].y);
}
int main()
{
    f=fopen("infasuratoare.in","r");g=fopen("infasuratoare.out","w");
    Read();Solve();Displaying();
    fclose(f);fclose(g);
    return 0;
}