Pagini recente » Cod sursa (job #755723) | Cod sursa (job #264822) | Cod sursa (job #1307437) | Cod sursa (job #445504) | Cod sursa (job #556915)
Cod sursa(job #556915)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
#define x first
#define y second
const char Input[] = "infasuratoare.in";
const char Output[] = "infasuratoare.out";
const int Inf = 0x3f3f3f3f;
int N;
vector <int> st;
vector < pair <double, double> > P;
double Pnt( pair <double, double> A, pair <double, double> B ) {
if( A.x == B.x )
return Inf;
return (A.y - B.y) / (A.x - B.x);
}
double Sgn( pair <double, double> A, pair <double, double> B, pair <double, double> C ) {
return A.x * B.y + C.x * A.y + B.x * C.y - (C.x * B.y + B.x * A.y + A.x * C.y);
}
struct cmp {
bool operator()( pair <double, double> A, pair <double, double> B ) {
return Pnt( P[0], A ) < Pnt( P[0], B );
}
};
int main() {
ifstream fin( Input );
ofstream fout( Output );
int i;
fin >> N;
P.resize( N );
for( i = 0; i < N; ++i ) {
fin >> P[i].x >> P[i].y;
if( P[i].x < P[0].x )
swap( P[i], P[0] );
else if( P[i].x == P[0].x && P[i].y < P[0].y )
swap( P[i], P[0] );
}
sort( P.begin() + 1, P.end(), cmp() );
for( i = 0; i < N; ++i ) {
while( st.size() > 2 && Sgn( P[st[st.size() - 2]], P[st[st.size() - 1]], P[i] ) < 0 )
st.pop_back();
st.push_back( i );
}
fout << st.size() << "\n";
for( i = 0; i < (int)st.size(); ++i )
fout << P[st[i]].x << " " << P[st[i]].y << "\n";
fin.close();
fout.close();
return 0;
}