Pagini recente » Cod sursa (job #2655255) | Cod sursa (job #2655157) | Cod sursa (job #2556051) | Cod sursa (job #3260928) | Cod sursa (job #2576495)
#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, [pivot](Point A, Point B){return det(points[pivot], A, B) > 0;});
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]) == false) --head;
points_stack[++head] = points[i];
}
fout << fixed;
fout << head << '\n';
for(int i = 1; i <= head; ++i)
fout << setprecision(6) << points_stack[i].first << ' ' << points_stack[i].second << '\n';
}