Pagini recente » Cod sursa (job #748389) | Cod sursa (job #1020642) | Cod sursa (job #544894) | Cod sursa (job #3309205) | Cod sursa (job #3309650)
#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
pair <double,double> v[120021];
vector <pair <double,double>> ans;
double Determinant(double x1,double y1,double x2,double y2,double x3,double y3){
return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
}
bool Comp(pair <double,double> a,pair <double,double> b){
if (Determinant(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0) return 1;
if (Determinant(v[0].x,v[0].y,a.x,a.y,b.x,b.y)<0) return 0;
return a.x<b.x;
}
signed main()
{
int n;
fin >> n;
fin >> v[0].x >> v[0].y;
for (int i=1;i<n;++i){
fin >> v[i].x >> v[i].y;
if (v[i].x<v[0].x or (v[i].x==v[0].x and v[i].y<v[0].y)) swap(v[0],v[i]);
}
v[n] = v[0];
sort(v+1,v+n,Comp);
ans.push_back(v[0]);
for (int i=1;i<=n;++i){
bool loob = 1;
while (ans.size()>=2 and loob){
loob = 0;
pair <double,double> alfa = ans.back();
ans.pop_back();
if (Determinant(ans.back().x,ans.back().y,alfa.x,alfa.y,v[i].x,v[i].y)<=0) loob = 1;
else ans.push_back(alfa);
}
ans.push_back(v[i]);
}
ans.pop_back();
fout << ans.size() << '\n';
for (auto x:ans){
fout << setprecision(8) << fixed << x.x << ' ' << x.y << '\n';
}
return 0;
}