Pagini recente » joaca_4 | Cod sursa (job #1449845) | Cod sursa (job #1956439) | Cod sursa (job #398410) | Cod sursa (job #2030362)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX = 120010;
struct Point{
double x, y;
};
Point A;
void ReadPoints( Point a[MAX], int& N );
void GrahamScan( Point a[MAX], Point st[MAX], int N, int& top );
void Sort( Point a[MAX], int N );
double CrossProduct( Point a, Point b, Point c );
void Write( Point st[MAX], int N );
bool CompPoints( const Point& p1, const Point& p2 );
int main()
{
Point a[MAX], res[MAX];
int N, M;
ReadPoints(a, N);
GrahamScan(a, res, N, M);
Write(res, M);
fin.close();
fout.close();
return 0;
}
void ReadPoints( Point a[MAX], int& N )
{
fin >> N;
for ( int i = 1; i <= N; ++i )
fin >> a[i].x >> a[i].y;
}
void GrahamScan( Point a[MAX], Point st[MAX], int N, int& top )
{
Sort(a, N);
top = 2;
st[1] = a[1];
st[2] = a[2];
for ( int i = 3; i <= N; ++i )
{
while (top >= 2 && CrossProduct(st[top - 1], st[top], a[i]) < 0)
--top;
st[++top] = a[i];
}
}
void Sort( Point a[MAX], int N )
{
for ( int i = 2; i <= N; ++i )
if ( a[i].y < a[1].y || ( a[i].y == a[1].y && a[i].x < a[1].x ) )
swap(a[i], a[1]);
A = a[1];
sort(a + 2, a + N + 1, CompPoints);
}
double CrossProduct( Point a, Point b, Point c )
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
void Write( Point st[MAX], int N )
{
fout << N << '\n';
for ( int i = 1; i <= N; ++i )
fout << fixed << setprecision(12) << st[i].x << ' ' << st[i].y << '\n';
}
bool CompPoints( const Point& p1, const Point& p2 )
{
return CrossProduct(A, p1, p2) > 0;
}