Pagini recente » Cod sursa (job #1938396) | Cod sursa (job #1354769) | Cod sursa (job #2004663) | Cod sursa (job #1543325) | Cod sursa (job #2576525)
#include <bits/stdc++.h>
using namespace std;
typedef pair<long double, long double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N_MAX = 12e4 + 1;
int N;
vector<Point> points(N_MAX);
inline bool det(Point& A, Point& B, Point& C){ return (A.first*B.second + B.first*C.second + C.first*A.second - B.second*C.first - C.second*A.first - A.second*B.first) > 0;}
int head;
vector<Point> points_stack(N_MAX);
int main()
{
fin >> N;
int pivot = 1;
for(int i = 1; i <= N; ++i)
{
fin >> points[i].first >> points[i].second;
if(points[i] < points[pivot]) pivot = i;
}
swap(points[1], points[pivot]);
sort(points.begin() + 2, points.begin() + N + 1, [](Point& A, Point& B){return det(points[1], A, B) == false;});
points_stack[1] = points[1];
points_stack[2] = points[2];
head = 2;
for(int i = 3; i <= N; ++i)
{
while(head >= 2 && det(points_stack[head - 1], points_stack[head], points[i]) == true) --head;
points_stack[++head] = points[i];
}
fout << fixed;
fout << head << '\n';
for(int i = head; i >= 1; --i)
fout << setprecision(6) << points_stack[i].first << ' ' << points_stack[i].second << '\n';
}