Pagini recente » Istoria paginii runda/dasdasd/clasament | Monitorul de evaluare | Istoria paginii runda/concur/clasament | Monitorul de evaluare | Cod sursa (job #1349969)
#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) /* se verifica daca punctul C(care este testat) se afla de o parte sau alta a dreptei AB
utilizandu-se formula cu determinanti a ariei triunghiului ABC */
{
double A,B,C;
A = a.y-b.y;
B = b.x-a.x;
C = a.x*b.y - b.x*a.y;
return cmp1(A*c.x+B*c.y+C,0);
}
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&&verif(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=1;i<=h;i++)
{
fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
}
fout.close();
return 0;
}