Pagini recente » Cod sursa (job #1220271) | Cod sursa (job #1794665) | Cod sursa (job #2344499) | Cod sursa (job #2488709) | Cod sursa (job #2793389)
#include<bits/stdc++.h>
using namespace std ;
using Point = complex<double>;
const double kPi = 4.0 * atan(1.0);
const double kEps = 1e-9; // Good eps for long double is ~1e-11
#define X() real()
#define Y() imag()
double dot(Point a, Point b) { return (conj(a) * b).X(); }
double cross(Point a, Point b) { return (conj(a) * b).Y(); }
double dist(Point a, Point b) { return abs(b - a); }
Point perp(Point a) { return Point{-a.Y(), a.X()}; } // +90deg
Point rotateCCW(Point a, double theta) {
return a * polar(1.0, theta); }
double det(Point a, Point b, Point c) {
return cross(b - a, c - a); }
// abs() is norm (length) of vector
// norm() is square of abs()
// arg() is angle of vector
// det() is twice the signed area of the triangle abc
// and is > 0 iff c is to the left as viewed from a towards b.
// polar(r, theta) gets a vector from abs() and arg()
void ExampleUsage() {
Point a{1.0, 1.0}, b{2.0, 3.0};
cerr << a << " " << b << endl;
cerr << "Length of ab is: " << dist(a, b) << endl;
cerr << "Angle of a is: " << arg(a) << endl;
cerr << "axb is: " << cross(a, b) << endl;
}
using Poly = vector<Point>;
pair<Poly, Poly> ConvexHull(Poly P) {
sort(P.begin(), P.end(), [](Point a, Point b) {
return make_pair(a.X(), a.Y()) < make_pair(b.X(), b.Y());
});
P.erase(unique(P.begin(), P.end()), P.end());
Poly up, dw;
for (auto p : P) {
while (up.size() >= 2 &&
det(up[up.size() - 2], up.back(), p) > 0) // (1)
up.pop_back();
up.push_back(p);
while (dw.size() >= 2 &&
det(dw[dw.size() - 2], dw.back(), p) < 0) // (2)
dw.pop_back();
dw.push_back(p);
}
return { up , dw } ;
}
#define MAXN 120007
int n ;
pair < double , double > a[ MAXN ] ;
Poly aux ;
void input ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ].first >> a[ i ].second ;
aux.push_back ( { a[ i ].first , a[ i ].second } ) ;
}
}
void solve ( ) {
auto ret = ConvexHull ( aux ) ;
cout << ret.first.size ( ) + ret.second.size ( ) - 2 << "\n" ;
ret.second.pop_back ( ) ;
reverse ( ret.second.begin ( ) , ret.second.end ( ) ) ;
ret.second.pop_back ( ) ;
reverse ( ret.first.begin ( ) , ret.first.end ( ) ) ;
reverse ( ret.second.begin ( ) , ret.second.end ( ) ) ;
swap ( ret.first , ret.second ) ;
for ( auto e : ret.first ) {
cout << fixed << setprecision ( 12 ) << e.X() << " " << e.Y() << "\n" ;
}
for ( auto e : ret.second ) {
cout << fixed << setprecision ( 12 ) << e.X() << " " << e.Y() << "\n" ;
}
}
int main ( ) {
freopen ( "infasuratoare.in" , "r" , stdin ) ;
freopen ( "infasuratoare.out" , "w" , stdout ) ;
/// ios_base :: sync_with_stdio ( false ) ;
/// cin.tie ( NULL ) ;
int t ;
t = 1 ;
/// scanf ( "%d" , &t ) ;
/// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}