Cod sursa(job #1350013)

Utilizator StefanMudragMudrag Stefan StefanMudrag Data 20 februarie 2015 16:52:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#define NMAX 120011
#define eps 1e-12
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x,y;
int id;};
punct v[NMAX];
int n,s[NMAX],h,ok[NMAX];
void read()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y,v[i].id=i;

    fin.close();
}
int cmp1(double a,double b)
{
    if(a+eps<b) return 1;
    if(b+eps<a)return -1;
    return 0;
}
bool cmp(const punct &a,const punct &b)
{
    int t;
    t=cmp1(a.x,b.x);
    if(t!=0)return t==1;
    return (cmp1(a.y,b.y)==1);
}
int semn(punct &a, punct &b, punct &c)
{
    double det=a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
    if (det==0) return 0;
    return (det<0)?(-1):1;
}
int verif(punct a,punct b,punct c)
{

    return cmp1((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y),0);

}
void solve()
{
    sort(v+1,v+n+1,cmp);
    int q,k,i=3;
    s[1]=1;s[2]=2;
    k=2;q=1;ok[2]=1;

    while(!ok[1])
    {

        while(ok[i])
        {
            if(i==n)q=-1;
            i+=q;
        }
        while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
        {

            ok[s[k--]]=0;


        }

        s[++k]=i;
        ok[i]=1;
    }
  h=k-1;
}
int main()
{
    read();
    solve();
    fout<<setprecision(6)<<fixed;
    fout<<h<<'\n';

   for(int i=2;i<=h+1;i++)
   {
       fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
   }
fout.close();
return 0;

}