Pagini recente » Cod sursa (job #2549275) | Cod sursa (job #1074254) | Cod sursa (job #2440203) | Cod sursa (job #2818374) | Cod sursa (job #3203411)
#include <bits/stdc++.h>
#define N 120008
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, k;
struct point{
double x, y;
bool operator!=(point A){
return A.x != x || A.y != y;
}
bool operator==(point A){
return A.x == x && A.y == y;
}
} v[N], sol[N];
void Citire()
{
int i;
fin >> n;
for( i=1; i<=n; i++ ){
fin >> v[i].x >> v[i].y;
}
}
int Orientare( point A, point B, point C )
{
if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) < 0 )
return -1;
if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) > 0 )
return 1;
return 0;
}
double dist( point A, point B ){
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
bool cmp( point A, point B )
{
return Orientare( v[1], A, B ) > 0;
}
point st[N];
int top;
void Rezolvare()
{
int i, p;
point P;
double ymn = 2e9;
for( i=1; i<=n; i++ ){
if( v[i].y < ymn ){
ymn = v[i].y;
P = v[i];
p = i;
}
else if( v[i].y == ymn ) if( v[i].x < P.x ){
P = v[i];
p = i;
}
}
swap( v[1], v[p] );
sort( v + 2, v + n + 1, cmp );
st[++top] = v[1];
st[++top] = v[2];
for( i=3; i<=n; i++ ){
while( top >= 2 && Orientare( st[top - 1], st[top], v[i] ) <= 0 ) top--;
st[++top] = v[i];
}
fout << top << "\n";
fout << fixed << setprecision(12);
for( i=1; i<=top; i++ ){
fout << st[i].x << " " << st[i].y << "\n";
}
}
int main()
{
Citire();
Rezolvare();
return 0;
}