Pagini recente » Cod sursa (job #2030762) | Cod sursa (job #311148) | Cod sursa (job #1713747) | Cod sursa (job #1647931) | Cod sursa (job #2371389)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;
vector < int > S;
struct punct
{
double x,y;
};
double X=1000000005,Y=1000000005;
int low,N;
punct A[NMAX];
int pula( punct A, punct B , punct C)
{
long long rez=1LL*(A.y - B.y) * 1LL*(B.x-C.x) - 1LL*(B.y-C.y) * 1LL*(A.x-B.x);
if( rez < 0 ) return 1;
else if(rez > 0 ) return -1;
else return 0;
}
bool comp( punct C , punct B)
{
return ( pula ( A[1], C , B) == 1 );
}
void read()
{
fin>>N;
for(int i=1;i<=N;++i)
{
fin>>A[i].x>>A[i].y;
if(A[i].y<Y)
{
Y=A[i].y;
X=A[i].x;
low=i;
}
else
if(A[i].y==Y && A[i].x<X)
{
X=A[i].x;
low=i;
}
}
swap(A[low],A[1]);
sort(A+1,A+N+1,comp);
S.push_back(1);
S.push_back(2);
for(int i=3;i<=N;++i)
{
while(pula( A[S[S.size()-2]] ,A[ S.back() ], A[i]) < 0)
S.pop_back();
S.push_back(i);
}
fout<<S.size()<<"\n";
for(int i=0;i<S.size();++i) fout<<fixed<<setprecision(6)<<A[S[i]].x<<" "<<A[S[i]].y<<"\n";
}
int main()
{
read();
return 0;
}