Pagini recente » Cod sursa (job #1528215) | Cod sursa (job #2110654) | Cod sursa (job #1073442) | Cod sursa (job #1796413) | Cod sursa (job #1651385)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define point pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
pair <double,double> p[120001];
int n,mn,st[120001],top;
double det(point x,point y,point z)
{
return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}
bool cmp(point x,point y)
{
return det(p[1],x,y)>0;
}
int main()
{
f>>n;
mn=1;
for(int i=1;i<=n;i++)
{
f>>p[i].first>>p[i].second;
if(p[i].second<p[mn].second) mn=i;
else if(p[i].second==p[mn].second and p[i].first<p[mn].first) mn=i;
}
swap(p[1],p[mn]);
sort(p+2,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(top>=2 and det(p[i],p[st[top]],p[st[top-1]])>0) top--;
st[++top]=i;
}
g<<top<<'\n';
for(int i=1;i<=top;i++)
{
g<<fixed<<setprecision(6)<<p[st[i]].first<<" "<<p[st[i]].second<<'\n';
}
return 0;
}