Pagini recente » Cod sursa (job #627380) | Cod sursa (job #1906047) | Cod sursa (job #3189823) | Cod sursa (job #1965334) | Cod sursa (job #3207013)
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
int m, n;
struct el
{
double x, y;
}v[120005];
double dist(el a, el b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int orientation(el a, el b, el c)
{
double val = (b.y - a.y) * (c. x - b.x) - (b. x - a.x) * (c. y - b.y);
if(val == 0) // coliniaritate
{
return 0;
}
else
{
if(val > 0)
{
return 1; // inv trigo
}
else
{
return 2; // trigo
}
}
}
el elem;
el stiv(stack<el>&S)
{
el aux = S.top();
S.pop();
el auxi = S.top();
S.push(aux);
return auxi;
}
void schimba(el &p1, el &p2)
{
el auxi = p1;
p1 = p2;
p2 = auxi;
}
bool compara(el p1, el p2)
{
int t = orientation(elem, p1, p2);
if(t == 0)
{
return (dist(elem, p2) >= dist(elem, p1)?-1:1);
}
return ((t == 2)?-1:1);
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
void convexhull(el points[], int n)
{
double ymin = points[1].y;
int mini = 1;
for(int i = 2; i <= n; ++i)
{
double u = points[i].y;
if((u < ymin) || (u == ymin && points[i]. x < points[mini].x))
{
ymin = u;
mini = i;
}
}
schimba(points[1], points[mini]);
elem = points[1];
sort(points + 2, points + n + 1, compara);
m = 1;
for(int i = 2; i <= n; ++i)
{
while(i < n && orientation(elem, points[i], points[i + 1]) == 0)
{
i++;
}
points[m] = points[i];
m++;
}
if(m < 3)
{
return;
}
stack<el>stiva;
stiva.push(points[1]);
stiva.push(points[2]);
stiva.push(points[3]);
for(int i = 4; i <= m; ++i)
{
while(stiva.size() > 1 && orientation(stiv(stiva), stiva.top(), points[i]) != 2)
{
stiva.pop();
}
stiva.push(points[i]);
}
fout << stiva.size() << '\n';
while(!stiva.empty())
{
fout << fixed << setprecision(6) << (double)stiva.top().x << " ";
fout << fixed << setprecision(6) << (double)stiva.top().y << '\n';
stiva.pop();
}
}
int32_t main(int argc, char * argv[])
{
fin >> n;
for(int i = 1; i <= n; ++i)
{
fin >> v[i].x >> v[i].y;
}
convexhull(v, n);
return 0;
}