Pagini recente » Cod sursa (job #688735) | Cod sursa (job #2941266) | Cod sursa (job #508873) | Cod sursa (job #2848360) | Cod sursa (job #3224702)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int64_t n, i, k, cmin, m=1;
struct coord{int64_t x, y;};
coord v[MAX];
stack<coord> s, r;
coord nextToTop()
{
coord p = s.top();
s.pop();
coord res = s.top();
s.push(p);
return res;
}
int64_t dist(coord p1, coord p2)
{
const int64_t o1=(p1.x-p2.x), o2=(p1.y-p2.y);
return o1*o1+o2*o2;
}
int64_t orientatie(coord p1, coord p2, coord p3)
{
int64_t val = (p2.y-p1.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p2.x-p1.x);
if(val == 0) return 0;
else return (val > 0 ? 1 : 2);
}
bool compare(const coord i1, const coord i2)
{
const int64_t o = orientatie(v[0], i1, i2);
if(!o) return (dist(v[0], i2) >= dist(v[0], i1));
else return (o == 2);
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> v[0].x >> v[0].y;
for(i=1; i < n; i++)
{
fin >> v[i].x >> v[i].y;
if((v[i].y < v[cmin].y) || ((v[i].y == v[cmin].y) && (v[i].x < v[cmin].x))) cmin = i;
}
swap(v[0], v[cmin]);
sort(v+1, v+n, compare);
for(i=1; i < n; i++)
{
while((i < n-1) && (!orientatie(v[0], v[i], v[i+1]))) i++;
v[m++] = v[i];
}
s.push(v[0]);
s.push(v[1]);
s.push(v[2]);
for(i=3; i < m; i++)
{
while(s.size() > 1 && orientatie(nextToTop(), s.top(), v[i]) != 2) s.pop();
s.push(v[i]);
}
while(!s.empty())
{
r.push(s.top());
s.pop();
}
fout << r.size() << '\n';
while(!r.empty())
{
fout << r.top().x << ' ' << r.top().y << '\n';
r.pop();
}
}