Pagini recente » Cod sursa (job #2556507) | Cod sursa (job #1445770) | Cod sursa (job #325398) | Istoria paginii runda/cerc_micutzii/clasament | Cod sursa (job #1921186)
#include <bits/stdc++.h>
using namespace std;
struct dot{
double x;
double y;
};
dot t[120000],stck[120000];
double f(dot a, dot b, dot c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
bool cmp(dot a, dot b)
{
return (f(t[1],a,b) < 0);
}
int n,i,poz,st=1000000001,js=1000000001;
int main()
{
ifstream cin("infasuratoare.in");
ifstream cout("infasuratoare.out");
cin>>n;
for (i=1; i<=n; i++)
cin>>t[i].x>>t[i].y;
for (i=1; i<=n; i++)
{
if (t[i].x<st) st=t[i].x,js=t[i].y,poz=i; else
if (t[i].x==st) if (t[i].y<js) js=t[i].y,poz=i;
}
swap(t[1],t[poz]);
sort(t+2,t+n+1,cmp);
stck[1]=t[1];
stck[2]=t[2];
int last=2;
for (i=3; i<=n; i++)
{
while (last>=2 && f(stck[last-1],stck[last],t[i])>0) last--;
last++;
stck[last]=t[i];
}
cout<<last<<'\n';
for (i=last-1; i>=1; i--)
cout<<setprecision(12)<<fixed<<stck[i].x<<" "<<stck[i].y<<'\n';
cout<<setprecision(12)<<fixed<<stck[last].x<<" "<<stck[last].y<<'\n';
}