Pagini recente » Cod sursa (job #578050) | Cod sursa (job #1629570) | Cod sursa (job #1729821) | Cod sursa (job #2282529) | Cod sursa (job #2110090)
#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 (x == other.x)return y < other.y;
return x < other.x;
}
}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;
top = 1;
///det < 0 => stanga
///det = 0 => coliniare
///det > 0 => dreapta
for (int i = 2; 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;
}