Pagini recente » Cod sursa (job #2104940) | Monitorul de evaluare | Cod sursa (job #943679) | Cod sursa (job #2071718) | Cod sursa (job #2280334)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Point{
double x,y;
}pt[120005],S[120005],aux;
int n,i,vf,poz;
double det(Point A, Point B, Point C)
{
return A.x * B.y + B.x * C.y + A.y * C.x - C.x * B.y - C.y * A.x - A.y * B.x;
}
bool cmp1 (Point A, Point B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
bool cmp (Point A, Point B){
return det(pt[1],A,B) < 0;
}
int main()
{
cin>>n;
aux.x = 2000000000;
aux.y = 2000000000;
for(i=1; i<=n; ++i)
cin>>pt[i].x>>pt[i].y;
sort(pt+1,pt+n+1,cmp1);
sort(pt+2,pt+n+1,cmp);
S[1] = pt[1];
S[2] = pt[2];
S[3] = pt[3];
vf = 3;
for(int i=4; i <= n; i++)
{
while(det(S[vf-1], S[vf], pt[i]) > 0)
vf--;
vf++;
S[vf] = pt[i];
}
cout<<vf<<"\n";
for(i=vf;i>=1;--i)
cout<<setprecision(12)<<fixed<<S[i].x<<" "<<S[i].y<<"\n";
return 0;
}