Pagini recente » Cod sursa (job #891445) | Cod sursa (job #1644118) | Cod sursa (job #2749668) | Cod sursa (job #1512703) | Cod sursa (job #2500721)
#include <iostream>
#include <fstream>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;
const int nm=120000;
struct nod{long double x,y,u;}pct[nm];
bool u[nm];
long double xc,yc;
int i,n,p,ul,aul;
int f(nod a, nod b)
{
return a.u>b.u;
}
deque<int>co;
double tri(int i, int j, int k)
{
return pct[i].x*pct[j].y+pct[j].x*pct[k].y+pct[i].y*pct[k].x-pct[j].y*pct[k].x-pct[i].y*pct[j].x-pct[i].x*pct[k].y;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin>>n;
for(i=1;i<=n;i++){fin>>pct[i].x>>pct[i].y;xc+=pct[i].x;yc+=pct[i].y;}
xc/=n;yc/=n;
for(i=1;i<=n;i++)pct[i].u=atan2((xc-pct[i].x),(yc-pct[i].y));
sort(pct+1,pct+n+1,f);
p=1;
for(i=1;i<=n;i++)
if((pct[p].y>pct[i].y)||((pct[p].y==pct[i].y)&&(pct[p].x>pct[i].x)))p=i;
for(i=1;i<p;i++)pct[n+i]=pct[i];
for(i=1;i<=n;i++)pct[i]=pct[p+i-1];
co.push_back(1);
co.push_back(2);
p=3;
while(p<=n)
{
ul=co.back();co.pop_back();
aul=co.back();
if(tri(aul,ul,p)>=0){co.push_back(ul);co.push_back(p);}
else
{
while(tri(aul,ul,p)<0&&(aul!=1))
{
ul=aul;
aul=co.back();co.pop_back();
};
co.push_back(p);
}
p++;
}
fout<<co.size()<<"\n";
while(!co.empty()){ p=co.front();fout<<pct[p].x<<" "<<pct[p].y<<"\n";co.pop_front();}
return 0;
}