Pagini recente » Istoria paginii runda/simulare_oji_09_03_2023 | Cod sursa (job #2045958) | Cod sursa (job #2643071) | Cod sursa (job #719814) | Cod sursa (job #1471568)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n, pos;
pair < double, double > V[120010];
int S[120010], top;
double Produs(pair < double, double > a, pair < double, double > b, pair < double, double > c)
{
return ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y));
}
bool cmp(pair < double, double > a, pair < double, double > b)
{
return (Produs(V[1], a, b) < 0);
}
int main()
{
fin >> n;
pos = 1;
for (int i = 1; i <= n; i++)
{
fin >> V[i].x >> V[i].y;
if (V[i] < V[pos])
{
pos = i;
}
}
swap(V[1], V[pos]);
sort(V + 2, V + 1 + n, cmp);
S[++top] = 1;
for (int i = 2; i <= n; i++)
{
while (top > 1 && Produs(V[S[top - 1]], V[S[top]], V[i]) > 0)
{
top--;
}
S[++top] = i;
}
fout << top << '\n';
while (top)
{
fout << fixed << setprecision(6) << V[S[top]].x << ' ' << V[S[top]].y << '\n';
top--;
}
fout.close();
return 0;
}