Pagini recente » Cod sursa (job #1739922) | Cod sursa (job #2498247) | Cod sursa (job #932895) | Cod sursa (job #2986320) | Cod sursa (job #1922719)
#include <fstream>
#include <algorithm>
#include <vector>
//#include <iostream>
#include <iomanip>
#include <limits>
#define nmax 120009
using namespace std;
int xmin,ymin;
struct punct{
double x,y,tg;
}p[nmax];
vector<int> S;
bool cmp(punct a,punct b){
return a.tg<b.tg;
}
bool arie(double x1,double y1,double x2,double y2,double x3,double y3){
double arie=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
return arie>=0;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main(){
int n,i;
fin>>n;
int org=1;
for(i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
if(p[org].x > p[i].x || (p[org].x==p[i].x && p[org].y>p[i].y))org=i;
}
xmin=p[org].x;
ymin=p[org].y;
swap(p[1],p[org]);
p[1].x=0;p[1].y=0;
p[n+1]=p[1];
for(i=2;i<=n;i++)
{
p[i].x-=xmin;
p[i].y-=ymin;
if(p[i].x==0)p[i].tg=numeric_limits<double>::max();
else p[i].tg=p[i].y/p[i].x;
}
sort(p+2,p+n+1,cmp);
int p1,p2,p3;
S.push_back(0);
S.push_back(1);
for(i=2;i<=n+1;i++)
{ p1=i;
p2=S[S.size()-1];S.pop_back();
p3=S[S.size()-1];
while(S.size()>1 && !arie(p[p3].x,p[p3].y,p[p2].x,p[p2].y,p[p1].x,p[p1].y))
{p2=S[S.size()-1];S.pop_back();
p3=S[S.size()-1];
}
S.push_back(p2);
S.push_back(p1);
}
fout<<S.size()-2<<'\n';
for(i=2; i<S.size(); i++)fout<<setprecision(8)<<fixed<<(p[S[i]].x+xmin)<<' '<<p[S[i]].y+ymin<<'\n';
}