Pagini recente » Cod sursa (job #688585) | Cod sursa (job #832299) | Cod sursa (job #541165) | Cod sursa (job #3177176) | Cod sursa (job #3207018)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double maximu = 1e9 + 55;
ll m;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct el
{
double x, y;
};
double dist(el a, el b)
{
return (a. x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double orientation(el a, el b, el c)
{
return (b. x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool compara(el a, el b)
{
ll p = orientation({0, 0}, a, b);
return p > 0;
}
void convexhull(el points[], int n)
{
double xmin = maximu, ymin = maximu;
for(int i = 0; i < n; ++i)
{
if(points[i].y < ymin)
{
xmin = points[i].x, ymin = points[i].y;
}
else
{
if(points[i].y == ymin && points[i].x < xmin)
{
xmin = points[i].x;
}
}
}
for(int i = 0; i < n; ++i)
{
points[i].x -= xmin;
points[i].y -= ymin;
if(points[i].x == 0 && points[i].y == 0)
{
swap(points[i], points[0]);
}
}
sort(points + 1, points + n, compara);
el stiva[120005] = {0};
stiva[0].x = points[0].x;
stiva[0].y = points[0].y;
stiva[1].x = points[1].x;
stiva[1].y = points[1].y;
m = 2; // presupunem ca avem minim 2 puncte in hull mai corect ar fi fost sa fac cu 3
ll dim = 2;
for(int i = 2; i < n; ++i)
{
while(orientation(stiva[dim - 2], stiva[dim - 1], points[i]) < 0)
{
dim--;
}
stiva[dim].x = points[i].x;
stiva[dim].y = points[i].y;
dim++;
}
// actualizam noua dimensiune la hull
m = dim;
fout << m << '\n';
for(int i = 0; i < m; ++i)
{
stiva[i].x += xmin;
stiva[i].y += ymin;
fout << fixed << setprecision(6) << (double)stiva[i].x << " ";
fout << fixed << setprecision(6) << (double)stiva[i].y << '\n';
}
}
el v[120005];
ll n;
int32_t main(int argc, char * argv[])
{
fin >> n;
for(int i= 0; i < n; ++i)
{
fin >> v[i].x >> v[i].y;
}
convexhull(v, n);
return 0;
}