Pagini recente » Cod sursa (job #3039230) | Cod sursa (job #1282399) | Cod sursa (job #1503681) | Cod sursa (job #2850111) | Cod sursa (job #2515485)
#include <bits/stdc++.h>
#define NM 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const long double EPS = 1e-12;
struct point
{
long double x, y;
point() {}
point(long double x, long double y): x(x), y(y) {}
point& operator+=(const point &t) {
x += t.x;
y += t.y;
return *this;
}
point& operator-=(const point &t) {
x -= t.x;
y -= t.y;
return *this;
}
point operator+(const point &t) const {
return point(*this) += t;
}
point operator-(const point &t) const {
return point(*this) -= t;
}
};
point v[NM];
point O = {0, 0};
int n, s1[NM], s2[NM], h1, h2;
long double cross(point A, point B)
{
return A.x*B.y - A.y*B.x;
}
bool turns_left(point A, point B, point C)
{
if(cross(B-A, C-B) > EPS)
return 1;
return 0;
}
bool cmp(point A, point B)
{
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool cmp2(point A, point B)
{
if(turns_left(O, A, B) > EPS)
return 1;
return 0;
}
int main()
{
fin >> n;
for(int i=1; i<=n; i++)
fin >> v[i].x >> v[i].y;
sort(v+1, v+1+n, cmp);
point first = v[1], last = v[n];
s1[++h1] = 1;
for(int i=2; i<n; i++)
if(turns_left(first, last, v[i]))
{
while(h1>=2 && turns_left(v[s1[h1-1]], v[s1[h1]], v[i]))
h1--;
s1[++h1] = i;
}
else
{
while(h2>=2 && !turns_left(v[s2[h2-1]], v[s2[h2]], v[i]))
h2--;
s2[++h2] = i;
}
s1[++h1] = n;
vector<point> sol;
for(int i=1; i<=h1; i++)
sol.push_back(v[s1[i]]);
for(int i=1; i<=h2; i++)
sol.push_back(v[s2[i]]);
sort(sol.begin(), sol.end(), cmp2);
fout << sol.size() << '\n';
fout << setprecision(12) << fixed;
for(auto it:sol)
fout << it.x << ' ' << it.y << '\n';
return 0;
}