Pagini recente » Cod sursa (job #2177274) | Cod sursa (job #1580240) | Cod sursa (job #70516) | Cod sursa (job #1262112) | Cod sursa (job #3148058)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
typedef long long ll;
const ll Nmax=1e5+20005, inf=1e9+5;
struct point{
double x, y;
};
ll distsq(point a, point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll det(point a, point b, point c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmpCH(point a, point b){
ll d=det({0, 0}, a, b);
if (d!=0)
return d>0;
return distsq({0, 0}, a)>distsq({0, 0}, b);
}
// vector / size of v / solution / size of sol
void convex_hull(point v[], ll n, point sol[], ll &m){ ///we take as many points
/// Graham scan from down-left most point
double mny=inf, mnx=inf;
for (ll i=0; i<n; i++)
if (v[i].y<mny){
mny=v[i].y;
mnx=v[i].x;
}
else if (v[i].y==mny && v[i].x<mnx)
mnx=v[i].x;
for (ll i=0; i<n; i++){///translation
v[i].x-=mnx;
v[i].y-=mny;
if (v[i].x==0 && v[i].y==0)
swap(v[i], v[0]);
}
sort (v+1, v+n, cmpCH); ///sort in order of the angle
ll i=2;
while (det(v[0], v[1], v[i])==0)
i++;
//reverse(v+1, v+i); ///reverse the first elements of the convex hull that are colinear with O(0, 0)
sol[0].x=v[0].x; sol[0].y=v[0].y;
sol[1].x=v[1].x; sol[1].y=v[1].y;
ll k=2;
for (ll i=2; i<n; i++){
while (det(sol[k-2], sol[k-1], v[i])<0)
k--;
sol[k].x=v[i].x;
sol[k].y=v[i].y;
k++;
}
m=k;
for (ll i=0; i<m; i++){
sol[i].x+=mnx;
sol[i].y+=mny;
}
}
ll n;
point v[Nmax], sol[Nmax];
int main()
{
fin>>n;
for (int i=0; i<n; i++)
fin>>v[i].x>>v[i].y;
ll m=0;
convex_hull(v, n, sol, m);
fout<<m<<'\n';
for (int i=0; i<m; i++)
fout<<sol[i].x<<' '<<sol[i].y<<'\n';
return 0;
}