Pagini recente » Cod sursa (job #315600) | Cod sursa (job #2224619) | Cod sursa (job #1678508) | Cod sursa (job #1671020) | Cod sursa (job #2557872)
#include <iostream>
#include <fstream>
#define N 120002
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream x("infasuratoare.in");
ofstream y("infasuratoare.out");
int n,ok,s[N];
bool viz[N];
struct elem
{
double xx,yy;
}v[N];
bool cmp(elem a, elem b)
{
if(a.xx==b.xx)
return a.yy<b.yy;
return a.xx<b.xx;
}
double det(elem A, elem B, elem C)
{
double a=A.xx,b=A.yy,c=B.xx,d=B.yy,e=C.xx,f=C.yy;
double delta=a*d+c*f+e*b-d*e-a*f-c*b;
return delta;
}
void rezolvare(int n, int &top)
{
int ok=1,i;
s[1]=1;
s[2]=2;
viz[2]=1;
top=2;
i=3;
while(!viz[1])
{
while(viz[i])
{
if(i==n)
ok=-1;
i+=ok;
}
while(det(v[s[top-1]],v[s[top]],v[i])<0 && top>=2)
viz[s[top]]=0,top--;
s[++top]=i;
viz[i]=1;
}
top--;
}
int main()
{
x>>n;
int top;
for(int i=1;i<=n;i++)
x>>v[i].xx>>v[i].yy;
sort(v+1,v+n+1,cmp);
rezolvare(n,top);
y<<top<<'\n';
for(int i=2;i<=top+1;i++)
y<<fixed<<setprecision(6)<<v[s[i]].xx<<" "<<v[s[i]].yy<<'\n';
x.close();
y.close();
return 0;
}