Pagini recente » Cod sursa (job #2743176) | Cod sursa (job #2488804) | Monitorul de evaluare | Cod sursa (job #2759645) | Cod sursa (job #2263025)
#include <bits/stdc++.h>
#define point std::pair <double, double>
#define x first
#define y second
#define MaxN 120005
std::ifstream InFile("infasuratoare.in");
std::ofstream OutFile("infasuratoare.out");
std::istream& operator >> (std::istream& Stream, point &Pair) {
return Stream >> Pair.first >> Pair.second;
}
inline double CrossProduct(point A, point B, point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int N;
point V[MaxN];
std::vector <point> Stack;
inline bool cmp(point P1, point P2) {
return CrossProduct(V[1], P1, P2) < 0;
}
void Sortare() {
int HullBegin = 0;
for (int i=1; i<N; ++i)
if (V[i] < V[HullBegin])
HullBegin = i;
std::swap(V[0], V[HullBegin]);
std::sort(V+1, V+N, cmp);
}
void ConvexHull() {
Sortare();
Stack.push_back(V[1]);
Stack.push_back(V[2]);
for (int i=2; i<N; ++i) {
while (Stack.size()>1
&& CrossProduct(Stack[Stack.size()-2], Stack[Stack.size()-1], V[i]) > 0)
Stack.pop_back();
Stack.push_back(V[i]);
}
}
void Citire() {
InFile >> N;
for (int i=0; i<N; ++i)
InFile >> V[i];
}
void Rezolvare() {
ConvexHull();
OutFile << Stack.size() << "\n";
OutFile << std::fixed << std::setprecision(6);
for (int i=Stack.size(); i>0; --i)
OutFile << Stack[i].x << ' ' << Stack[i].y << '\n';
}
int main() {
Citire();
Rezolvare();
return 0;
}