Pagini recente » Cod sursa (job #3245942) | Cod sursa (job #280762) | Cod sursa (job #1112597) | Cod sursa (job #1770822) | Cod sursa (job #3148054)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
typedef long long ll;
const ll Nmax=1e2+5, inf=1e9+5;
using pll=pair<ll, ll>;
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 dist(point a, point b){
return sqrt((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);
}
double pant(point a, point b){
if (a.x==b.x)
return -inf;
return (a.y-b.y)/(a.x-b.x);
}
double trarea(point a, point b, point c){
ll d=det(a, b, c);
if (d%2==0)
return d/2;
if (d>0)
return d/2+0.5;
return d/2-0.5;
}
void ecdr(point A, point B, ll &a, ll &b, ll&c){
a=A.y-B.y;
b=B.x-A.x;
c=A.x*(B.y-A.y)-A.y*(B.x-A.x);
}
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)
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;
}
for (ll i=0; i<m; i++){
sol[i].x+=mnx;
sol[i].y+=mny;
}
m=k;
}
int n;
point v[Nmax], sol[Nmax];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
int mny=inf, mnx=inf;
for (int i=0; i<n; i++)
cin>>v[i].x>>v[i].y;
ll m;
convex_hull(v, n, sol, m);
cout<<m<<'\n';
for (int i=0; i<m; i++)
cout<<sol[i].x<<' '<<sol[i].y<<'\n';
return 0;
}