Pagini recente » Cod sursa (job #2707804) | Cod sursa (job #2963675) | Cod sursa (job #2839588) | Cod sursa (job #1968252) | Cod sursa (job #2366817)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int NMAX=1e5+5;
struct punct {
double x,y;
};
int n;
punct P[NMAX];
vector <punct> hull;
double det(punct A,punct B,punct C)
{
return ((A.x*(B.y-C.y)+B.x*(C.y-A.y)+C.x*(A.y-B.y))<0);
}
int cmp(punct A,punct B)
{
if(A.x<B.x) return 1;
if(A.x>B.x) return 0;
return A.y<B.y;
}
int main()
{
fi>>n;
for(int i=1;i<=n;i++)
fi>>P[i].x>>P[i].y;
sort(P+1,P+n+1,cmp);
hull.push_back(P[1]);
hull.push_back(P[2]);
for(int i=3;i<=n;i++)
{
while(hull.size()>1 && det(hull[hull.size()-2],hull[hull.size()-1],P[i]))
hull.pop_back();
hull.push_back(P[i]);
}
for(int i=n-1;i>0;i--)
{
while(hull.size()>1 && det(hull[hull.size()-2],hull[hull.size()-1],P[i]))
hull.pop_back();
hull.push_back(P[i]);
}
hull.pop_back();
fo<<hull.size()<<"\n";
for(int i=0;i<hull.size();i++)
fo<<fixed<<setprecision(12)<<hull[i].x<<" "<<hull[i].y<<"\n";
fi.close();
fo.close();
return 0;
}