Pagini recente » Cod sursa (job #2466245) | Cod sursa (job #2188702)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#define INF 1000000002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{double x, y;};
int n;
Point p[120002];
vector<Point> co;
double sign(Point p1, Point p2, Point p3)
{
return (p1.x * p2.y + p1.y * p3.x + p2.x * p3.y) - (p2.y * p3.x + p2.x * p1.y + p1.x * p3.y);
}
bool test(Point p1, Point p2)
{
return sign(p[0], p1, p2) < 0;
}
int main()
{
fin >> n;
int maxX = -INF;
int pos = 0;
for(int i = 0; i < n; i ++)
{
fin >> p[i].x >> p[i].y;
if(p[i].x < p[pos].x || (p[i].x == p[pos].x && p[i].y < p[pos].y))
pos = i;
}
swap(p[0], p[pos]);
sort(p + 1, p + n, test);
co.push_back(p[0]);
for(int i = 1; i < n; i++)
{
while(co.size() > 1 && sign(co[co.size() - 2], co[co.size() - 1], p[i]) > 0)
co.pop_back();
co.push_back(p[i]);
}
fout << co.size() << '\n';
fout << fixed << setprecision(6);
for(int i = co.size() - 1; i >= 0; i --)
fout << co[i].x << ' ' << co[i].y << '\n';
return 0;
}