Pagini recente » Borderou de evaluare (job #2022046) | Cod sursa (job #3177308) | Borderou de evaluare (job #2334318) | Cod sursa (job #599420) | Cod sursa (job #2110073)
#include <bits/stdc++.h>
#define NMAX 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct hull
{
double x, y;
bool operator < (const hull &other)const{
if (y == other.y)return x < other.x;
return y < other.y;
}
}pct[NMAX];
int N, top;
int st[NMAX];
double det(int A, int B, int C)
{
/**
A x y 1
B x y 1
C x y 1
**/
return (pct[A].x * pct[B].y) + (pct[A].y * pct[C].x) + (pct[B].x * pct[C].y)
- (pct[C].x * pct[B].y) - (pct[C].y * pct[A].x) - (pct[B].x * pct[A].y);
}
int main()
{
fin >> N;
for (int i = 1; i <= N; i++)
fin >> pct[i].x >> pct[i].y;
sort(pct + 1, pct + N + 1);
st[1] = 1;
st[2] = 2;
top = 2;
///det < 0 => stanga
///det = 0 => coliniare
///det > 0 => dreapta
for (int i = 3; i <= N; i++)
{
while (top >= 2 && det(st[top - 1], st[top], i) >= 0)
--top;
st[++top] = i;
}
for (int i = N - 1; i >= 1; i--)
{
while (top >= 2 && det(st[top - 1], st[top], i) >= 0)
--top;
st[++top] = i;
}
top--;
fout << top << "\n";
for (int i = 1; i <= top; i++)
fout << fixed << setprecision(12) << pct[st[i]].x << " " << pct[st[i]].y << "\n";
return 0;
}