Pagini recente » Cod sursa (job #2512628) | Cod sursa (job #2507635) | Cod sursa (job #396685) | Cod sursa (job #1064195) | Cod sursa (job #2588416)
#include <bits/stdc++.h>
#define MAX 120000
#define INF 2e9
using namespace std;
struct Point
{
double x;
double y;
void operator=(const Point &other)
{
x = other.x;
y = other.y;
}
}v[MAX], stiva[MAX];
double crossProduct(const Point &a, const Point &b, const Point &c)
{
double x1 = b.x - a.x;
double y1 = b.y - a.y;
double x2 = c.x - a.x;
double y2 = c.y - a.y;
return y2 * x1 - y1 * x2;
}
bool greaterDistance(const Point &a, const Point &b, const Point &c)
{
double x1 = b.x - a.x;
double y1 = b.y - a.y;
double x2 = c.x - a.x;
double y2 = c.y - a.y;
return (x1 * x1 + y1 * y1) < (x2 * x2 + y2 * y2);
}
bool cmp(const Point &a, const Point &b)
{
return crossProduct(v[1], a, b) < 0;
}
int main()
{
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
ios::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
srand(time(NULL));
fin >> n;
int minPointX = 1;
for(int i = 1; i <= n; i++)
{
fin >> v[i].x >> v[i].y;
if(v[i].x < v[minPointX].x || (v[i].x == v[minPointX].x && v[i].y < v[minPointX].y))
minPointX = i;
}
swap(v[1], v[minPointX]);
sort(v + 2, v + 1 + n, cmp);
stiva[1] = v[1];
stiva[2] = v[2];
int head = 2;
for(int i = 3; i <= n; i++)
{
while(head >= 2 && crossProduct(stiva[head - 1], stiva[head], v[i]) > 0)
head--;
stiva[++head] = v[i];
}
fout << head << '\n';
fout << fixed;
fout.precision(12);
for(int i = head; i >= 1; i--)
fout << stiva[i].x << " " << stiva[i].y << '\n';
fin.close();
fout.close();
return 0;
}