Pagini recente » Cod sursa (job #356339) | Cod sursa (job #355120) | Cod sursa (job #2682821) | Cod sursa (job #562913) | Cod sursa (job #1142248)
#include<fstream>
#include<vector>
#include<algorithm>
#define INF 21000000
#define DMAX 12000
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,spoz,i;
struct punct{double x,y;}st[DMAX],pct;
vector<punct> v;
vector<punct>::iterator it;
int cmp(punct a, punct b)
{
double m1,m2;
if(a.x==v[0].x) m1=INF;
else m1=(a.y-v[0].y)/(a.x-v[0].x);
if(b.x==v[0].x) m2=INF;
else m2=(b.y-v[0].y)/(b.x-v[0].x);
return m1<m2;
}
int calc(punct A, punct B, punct C){return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}
int main()
{
fin>>n;
for(i=0;i<n;++i)
{
fin>>pct.x>>pct.y;
v.push_back(pct);
if(v[i].x<v[spoz].x || (v[i].x==v[spoz].x && v[i].y<v[spoz].y))
spoz=i;
}
swap(v[0],v[spoz]);
sort(v.begin()+1,v.end(),cmp);
st[1]=v[0];
st[2]=v[1];
int niv=2;
for(i=2;i<n;++i)
{
while(niv>=2 && calc(st[niv-1],st[niv],v[i])<0)
--niv;
st[++niv]=v[i];
}
for(i=1;i<=niv;++i)
fout<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}