Pagini recente » Cod sursa (job #2017201) | Cod sursa (job #1964554) | Cod sursa (job #2003617) | Cod sursa (job #1893314) | Cod sursa (job #2285940)
#include <cstdio>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair < double, double > PUNCT;
const int MAXN = 120000 + 16;
PUNCT InfCon[MAXN], Above[MAXN], Below[MAXN];
int N, AboveN, BelowN;
bool cmpPunct(PUNCT X, PUNCT Y)
{
if(X.second == Y.second)
return X.first < Y.first;
return X.second < Y.second;
}
double Sarrus(PUNCT, PUNCT, PUNCT);
void DivideMiddle();
void BuildAbove();
void BuildBelow();
void PutTogether();
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%i", &N);
for(int i = 1; i <= N; ++i)
scanf("%lf %lf", &InfCon[i].x, &InfCon[i].y);
sort(InfCon + 1, InfCon + N + 1, cmpPunct);
DivideMiddle();
BuildAbove();
BuildBelow();
PutTogether();
printf("%i\n", N);
for(int i = 1; i <= N; ++i)
printf("%.6lf %.6lf\n", InfCon[i].x, InfCon[i].y);
return 0;
}
void PutTogether()
{
N = 0;
for(int i = 1; i <= BelowN; ++i)
InfCon[++N] = Below[i];
for(int i = AboveN - 1; i > 1; --i)
InfCon[++N] = Above[i];
}
void BuildBelow()
{
bool Change;
do
{
Change = false;
int i = 2;
while(i < BelowN)
{
if(Sarrus(Below[i-1], Below[i], Below[i+1]) > 0)
i++;
else
{
Change = true;
for(int j = i; j < BelowN; ++j)
Below[j] = Below[j+1];
BelowN--;
}
}
} while(Change);
}
void BuildAbove()
{
bool Change;
do
{
Change = false;
int i = 2;
while(i < AboveN)
{
if(Sarrus(Above[i-1], Above[i], Above[i+1]) < 0)
i++;
else
{
Change = true;
for(int j = i; j < AboveN; ++j)
Above[j] = Above[j+1];
AboveN--;
}
}
} while(Change);
}
void DivideMiddle()
{
AboveN = BelowN = 1;
Above[1] = Below[1] = InfCon[1];
for(int i = 2; i < N; ++i)
if(Sarrus(InfCon[1], InfCon[i], InfCon[N]) < 0)
Above[++AboveN] = InfCon[i];
else
Below[++BelowN] = InfCon[i];
Above[++AboveN] = Below[++BelowN] = InfCon[N];
}
double Sarrus(PUNCT P1, PUNCT P2, PUNCT P3)
{
return P1.x * P2.y + P2.x * P3.y + P3.x * P1.y
-P3.x * P2.y - P2.x * P1.y - P1.x * P3.y;
}