Pagini recente » Cod sursa (job #2081219) | Cod sursa (job #2661358) | Cod sursa (job #271903) | Cod sursa (job #2627902) | Cod sursa (job #2700827)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int St[120005];
bool viz[120005];
struct node
{
double first,second;
};
node p[120005];
bool ok(node &a,node &b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
double det(node &a ,node &b,node &c)
{
return(b.first-a.first)*(c.second-b.second)-(b.second-a.second)*(c.first-b.first);
}
void solve(int &n,int &h)
{
sort(p+1,p+n+1,ok);
St[1]=1;
St[2]=2;
viz[2]=1;
int p=1;
for(int i=3;i>=1;i+=p)
{
if(viz[i]!=0) continue;
while(h>=2 && det(p[St[h-1]],p[St[h]],p[i])<0)
viz[St[h--]]=0;
St[++h]=i;
viz[i]=1;
if(i==n)
p-=1;
}
h--;
}
int main()
{
int n,h=2;
in>>n;
for(int i=1;i<=n;i++)
in>>p[i].first>>p[i].second;
solve(n,h);
out<<h<<"\n";
out<<fixed<<setprecision(6);
for(int i=1;i<=h;i++)
out<<p[St[i]].x<<" "<<p[St[i]].y<<"\n";
return 0;
}