Pagini recente » Cod sursa (job #1939782) | Cod sursa (job #1843215) | Cod sursa (job #905421) | Cod sursa (job #464380) | Cod sursa (job #2588317)
#include <bits/stdc++.h>
#define MAX 120000
#define INF 2e9
using namespace std;
struct Point
{
double x;
double y;
}v[MAX];
double crossProduct(Point a, Point b, 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(Point a, Point b, 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);
}
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)
minPointX = i;
}
vector<int>convexHull;
convexHull.push_back(minPointX);
int currentPoint = minPointX;
do
{
int nextPoint = currentPoint;
for(int i = 1; i <= n; i++)
{
if(i == currentPoint)continue;
if(crossProduct(v[currentPoint], v[nextPoint], v[i]) < 0)
nextPoint = i;
else if(crossProduct(v[currentPoint], v[nextPoint], v[i]) == 0)
if(greaterDistance(v[currentPoint], v[nextPoint], v[i]))
nextPoint = i;
}
convexHull.push_back(nextPoint);
currentPoint = nextPoint;
}while(currentPoint != convexHull[0]);
convexHull.pop_back();
fout << convexHull.size() << '\n';
fout << fixed;
fout.precision(12);
for(auto point : convexHull)
fout << v[point].x << " " << v[point].y << '\n';
fin.close();
fout.close();
return 0;
}