Pagini recente » Cod sursa (job #2467360) | Cod sursa (job #988318) | Istoria paginii runda/simumaster | Cod sursa (job #1394158) | Cod sursa (job #1662143)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000;
const double EPS = 1e-6;
struct PCT {
double x,y;
};
vector <PCT> v, hull;
int N;
double cross_product(PCT A, PCT O, PCT B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
bool cmp_PCT( PCT A, PCT B ) {
return ( A.x < B.x || (A.x == B.x && A.y < B.y) );
}
void make_hull( vector<PCT> pct, vector<PCT> &hull ) {
sort( pct.begin(), pct.end(), cmp_PCT );
hull.clear();
stack <int> st;
st.push( 0 ); st.push( 1 );
for( int i = 2; i < (int)pct.size(); ++i ) {
int ind2 = st.top();
st.pop();
int ind1 = st.top();
st.push(ind2);
while( (int)st.size()>1 && cross_product( pct[ind1], pct[ind2], pct[i] ) < EPS ) {
st.pop(); /// scot ind2
ind2 = st.top();
st.pop();
if( !st.empty() ) ind1 = st.top();
st.push(ind2);
}
st.push( i );
}
vector <PCT> sec;
while( !st.empty() ) {
hull.push_back( pct[ st.top() ] );
st.pop();
}
reverse( hull.begin(), hull.end() );
st.push( (int)pct.size() - 1 );
st.push( (int)pct.size() - 2 );
for( int i = (int)pct.size() - 3; i >= 0; --i ) {
int ind2 = st.top();
st.pop();
int ind1 = st.top();
st.push(ind2);
while( (int)st.size()>1 && cross_product( pct[ind1], pct[ind2], pct[i] ) < EPS ) {
st.pop(); /// scot ind2
ind2 = st.top();
st.pop();
if( !st.empty() ) ind1 = st.top();
st.push(ind2);
}
st.push( i );
}
while( !st.empty() ) {
sec.push_back( pct[ st.top() ] );
st.pop();
}
reverse( sec.begin(), sec.end() );
for( int i = 1; i < (int)sec.size() - 1; ++i ) hull.push_back( sec[i] );
reverse( hull.begin(), hull.end() );
}
int main() {
in >> N;
for( int i = 1; i <= N; ++i ) {
PCT p;
in >> p.x >> p.y;
v.push_back( p );
}
make_hull( v, hull );
out << hull.size() << '\n';
out << setprecision( 6 ) << fixed;
for( int i = 0; i < (int)hull.size(); ++i ) {
out << hull[i].x << ' ' << hull[i].y << '\n';
}
return 0;
}