Pagini recente » Cod sursa (job #2923181) | Cod sursa (job #924232) | Cod sursa (job #355039) | Cod sursa (job #1210916) | Cod sursa (job #1922675)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define nmax 120009
using namespace std;
int xmin,ymin;
void afisare();
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){
int 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;
cout<<n<<endl;
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=1<<30;
else p[i].tg=p[i].y/p[i].x;
}
sort(p+2,p+n+1,cmp);
/*
for(i=1;i<=n;i++)
cout<<p[i].x+xmin<<' '<<p[i].y+ymin<<' '<<p[i].tg<<endl;
cout<<arie(p[1].x,p[1].y,p[3].x,p[3].y,p[2].x,p[2].y)<<endl;
cout<<arie(p[1].x,p[1].y,p[3].x,p[3].y,p[4].x,p[4].y)<<endl;
cout<<endl;
*/
int p1,p2,p3;
S.push_back(0);
S.push_back(1);
for(i=2;i<=n+1;i++)
{S.push_back(i);
p1=S[S.size()-1];S.pop_back();
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))
{/*S.push_back(p1);
p1=S[S.size()-1];S.pop_back();*/
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';
/*
while(S.size()>1){
p1=S.top();S.pop();
cout<<p[p1].x+xmin<<' '<<p[p1].y+ymin<<'\n';
}*/
//afisare();
for(i=2; i<S.size(); i++)fout<<setprecision(8)<<fixed<<(p[S[i]].x+xmin)<<' '<<p[S[i]].y+ymin<<'\n';
}
/*
void afisare(){
if(S.size()>2){
int x=S.top();
S.pop();
afisare();
fout<<setprecision(6)<<fixed<<p[x].x+xmin<<' '<<p[x].y+ymin<<'\n';
}
}*/