Pagini recente » Cod sursa (job #694216) | Cod sursa (job #653104) | Cod sursa (job #2531922) | Cod sursa (job #16695) | Cod sursa (job #3215901)
#include <bits/stdc++.h>
#define NMAX 120003
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct point {
double x, y;
};
point points[NMAX], leftPoint;
int n, leftPointIndex;
vector<point> v;
double det(point a, point b, point c)
{
return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - a.x*c.y - c.x*b.y);
}
bool cmp(point a, point b)
{
return det(leftPoint, a, b) >= 0;
}
void read_data()
{
fin >> n;
for (int i = 0; i < n; i++)
{
double x, y;
fin >> x >> y;
points[i] = {x, y};
if (x < points[leftPointIndex].x || (x == points[leftPointIndex].x && y < points[leftPointIndex].y))
leftPointIndex = i;
}
}
int main()
{
read_data();
swap(points[0], points[leftPointIndex]); // fixam pct initial pe 0
leftPoint = points[0];
sort(points + 1, points + n, cmp);
v.push_back(leftPoint);
for (int i = 1; i < n; i++)
{
while (v.size() > 1 && det(v[v.size()-2], v[v.size()-1], points[i]) < 0)
v.pop_back();
v.push_back(points[i]);
}
fout << v.size() << "\n";
for (int i = 0; i < v.size(); i++)
fout << fixed << v[i].x << " " << v[i].y << "\n";
return 0;
}