Pagini recente » Cod sursa (job #2197090) | Cod sursa (job #300958) | Cod sursa (job #2865448) | Cod sursa (job #672374) | Cod sursa (job #2738280)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define x first
#define y second
typedef long double ld;
typedef pair<ld,ld> pii;
const int lim=12e4+5;
pii v[lim];
bool mycmp(pii a,pii b)
{
return (v[1].y-a.y)*(v[1].x-b.x)<(v[1].y-b.y)*(v[1].x-a.x);
}
vector<pii> ans;
int main()
{
int n;
in>>n;
for(int i=1;i<=n;++i)
in>>v[i].x>>v[i].y;
pii minim=v[1];
int unde=1;
for(int i=2;i<=n;++i)
if(v[i]<minim)
{
minim=v[i];
unde=i;
}
swap(v[1],v[unde]);
sort(v+2,v+n+1,mycmp);
ans.push_back(v[1]);
ans.push_back(v[2]);
int cnt=1;
for(int i=3;i<=n;++i)
{
while(ans.size()>=2 and (ans[cnt-1].y-ans[cnt].y)*(ans[cnt].x-v[i].x)>(ans[cnt].y-v[i].y)*(ans[cnt-1].x-ans[cnt].x))
ans.pop_back(),--cnt;
ans.push_back(v[i]);
++cnt;
}
out<<ans.size()<<'\n';
for(int i=0;i<ans.size();++i)
out<<fixed<<setprecision(6)<<ans[i].x<<' '<<ans[i].y<<'\n';
return 0;
}