Pagini recente » Cod sursa (job #177408) | Cod sursa (job #250928) | Cod sursa (job #450123) | Cod sursa (job #2080597) | Cod sursa (job #3162095)
#include <fstream>
#include <cmath>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 12e4;
struct Point
{
double x, y;
void Read()
{
cin >> x >> y;
}
bool operator < (const Point &other) const
{
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int n;
Point points[NMAX + 1];
Point stack[NMAX + 1];
int stackIndex;
double CrossProduct(Point p1, Point p2, Point p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
void Reverse(Point a[])
{
for(int i = 1, j = n; i < j; i++, j--)
swap(a[i], a[j]);
}
int GetCadran(Point p1)
{
if(p1.x >= 0 && p1.y >= 0)
return 1;
if(p1.x >= 0 && p1.y < 0)
return 2;
if(p1.x < 0 && p1.y < 0)
return 3;
return 4;
}
double Distance(Point p)
{
return p.x * p.x + p.y * p.y;
}
bool cmpT(Point p1, Point p2)
{
int cadran1 = GetCadran(p1);
int cadran2 = GetCadran(p2);
if(cadran1 != cadran2)
return cadran1 < cadran2;
double cross = CrossProduct({0, 0}, p1, p2);
if(cross != 0)
return cross > 0;
return Distance(p1) < Distance(p2);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
points[i].Read();
sort(points + 1, points + n + 1);
int bound = 2;
for(int rep = 0; rep < 2; rep++)
{
for(int i = 1; i <= n; i++)
{
while(stackIndex >= bound && CrossProduct(stack[stackIndex - 1], stack[stackIndex], points[i]) < 0)
stackIndex--;
stack[++stackIndex] = points[i];
}
stackIndex--;
bound += stackIndex;
Reverse(points);
}
cout << stackIndex << '\n';
for(int i = 1; i <= stackIndex; i++)
cout << stack[i].x << ' ' << stack[i].y << '\n';
return 0;
}