Pagini recente » Cod sursa (job #202539) | Cod sursa (job #3033401) | Cod sursa (job #2734063) | Cod sursa (job #941360) | Cod sursa (job #3225638)
#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define double long double
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;
using namespace std;
const double EPS = 1e-7;
/*******************************/
// INPUT / OUTPUT
#ifndef LOCAL
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define cin in
#define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS
int N;
struct Punct
{
double x, y;
} p0;
vector <Punct> puncte;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
cin >> N;
puncte.resize(N);
for (auto &p: puncte)
cin >> p.x >> p.y;
}
///-------------------------------------
inline int det(const Punct &a, const Punct &b, const Punct &c)
{
double o = (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);
if (fabs(o) <= EPS) return 0;
if (o > 0) return 1;
return -1;
}
///-------------------------------------
inline double dist2(const Punct &p)
{
return pow((p.x - p0.x), 2) + pow((p.y - p0.y), 2);
}
///-------------------------------------
inline bool cmp(const Punct &a, const Punct &b)
{
int o = det(p0, a, b);
if (o == 0)
{
return dist2(a) < dist2(b);
}
if (o == 1) return 0;
return 1;
}
///-------------------------------------
inline void Solution()
{
int min_idx = 0;
double min_y = puncte[0].y;
for (int i = 1 ; i < N ; ++ i)
{
if (puncte[i].y < min_y || (fabs(puncte[i].y - min_y) <= EPS && puncte[i].x < puncte[min_idx].x))
{
min_y = puncte[i].y;
min_idx = i;
}
}
swap(puncte[0], puncte[min_idx]);
p0 = puncte[0];
sort(puncte.begin() + 1, puncte.end(), cmp);
vector <Punct> st;
st.push_back(puncte[0]);
st.push_back(puncte[1]);
for (int i = 2 ; i < N ; ++ i)
{
while (st.size() >= 2 && det(st[st.size() - 1], st[st.size() - 2], puncte[i]) != 1)
st.pop_back();
st.push_back(puncte[i]);
}
cout << st.size() << "\n";
for (auto p: st)
cout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
}
///-------------------------------------
inline void Output()
{
}
///-------------------------------------
int main()
{
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
ReadInput();
Solution();
Output();
return 0;
}