Pagini recente » Cod sursa (job #932097) | Cod sursa (job #3191572) | Cod sursa (job #1245678) | Cod sursa (job #2333972) | Cod sursa (job #2565063)
#include<bits/stdc++.h>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int DIM = 120005;
const double EPS = 1e-12;
int N;
bool f[DIM];
vector<int> st;
punct arr[DIM];
double cross_product( punct S1, punct S2, punct P ){
return ( S2.x - P.x ) * ( S1.y - P.y ) - ( S1.x - P.x ) * ( S2.y - P.y );
}
int main(){
fin >> N;
for( int i = 1; i <= N; i++ )
fin >> arr[i].x >> arr[i].y;
sort( arr + 1, arr + N + 1 );
st.push_back(1);
st.push_back(2);
f[2] = true;
///lower_bound
for( int i = 3; i <= N; i++ ){
while( st.size() > 2 && cross_product( arr[ st[ st.size() - 2 ] ], arr[ st[ st.size() - 1 ] ], arr[i] ) < EPS )
f[ st.back() ] = false, st.pop_back();
f[i] = true;
st.push_back( i );
}
///upper_bound
for( int i = N; i >= 1; i-- ){
if( f[i] == true )
continue;
while( st.size() > 2 && cross_product( arr[ st[ st.size() - 2 ] ], arr[ st[ st.size() - 1 ] ], arr[i] ) < EPS )
f[ st.back() ] = false, st.pop_back();
f[i] = true;
st.push_back( i );
}
st.pop_back();
fout << (int)(st.size()) << "\n";
for( int i = st.size() - 1; i >= 0; i-- ){
fout << setprecision(10) << fixed << arr[ st[i] ].x << " " << arr[ st[i] ].y << "\n";
}
return 0;
}