Pagini recente » Cod sursa (job #1122263) | Cod sursa (job #1727746) | Cod sursa (job #1005900) | Cod sursa (job #2349068) | Cod sursa (job #1589862)
#include <algorithm>
#include <iomanip>
#include <fstream>
#define NMAX 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,nr=2;
struct punct{
double x,y;
}p[NMAX],S[NMAX];
inline double unghi(int nr,punct a,punct b){
return p[nr].x*a.y+p[nr].y*b.x+a.x*b.y-a.y*b.x-p[nr].x*b.y-p[nr].y*a.x;
}
inline bool comp(punct a,punct b){
return unghi(1,a,b)>0;
}
int main()
{
f>>n;
for (int i=1;i<=n;i++){
f>>p[i].x>>p[i].y;
if (p[i].x<p[1].x || (p[i].x==p[1].x && p[i].y<p[1].y))swap(p[1],p[i]);
}
sort(p+2,p+n+1,comp);
S[1]=p[1];S[2]=p[2];
for (int i=3;i<=n;i++){
while (nr>2 && unghi(nr-1,S[nr],p[i])<=0)nr--;
S[++nr]=p[i];
}
g<<nr<<fixed<<setprecision(6)<<'\n';
for (int i=1;i<=nr;i++)g<<S[i].x<<" "<<S[i].y<<'\n';
f.close();
g.close();
}