Pagini recente » Cod sursa (job #445113) | Cod sursa (job #1439600) | Cod sursa (job #3197038) | Cod sursa (job #3275729) | Cod sursa (job #2110162)
#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(hull A, hull B, hull C)
{
/**
A x y 1
B x y 1
C x y 1
**/
return (A.x * B.y) + (A.y * C.x) + (B.x * C.y)
- (C.x * B.y) - (C.y * A.x) - (B.x * A.y);
}
int cmp (hull A, hull B)
{
return det(pct[1], A, B) >= 0;
}
int main()
{
fin >> N;
for (int i = 1; i <= N; i++)
fin >> pct[i].x >> pct[i].y;
int pos = 1;
for (int i = 1; i <= N; i++)
if (pct[i] < pct[pos])
pos = i;
swap(pct[1], pct[pos]);
sort(pct + 2, pct + N + 1, cmp);
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(pct[st[top - 1]], pct[st[top]], pct[i]) <= 0)
--top;
st[++top] = i;
}
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;
}