Pagini recente » Cod sursa (job #2832948) | Cod sursa (job #172360) | Cod sursa (job #1936162) | Cod sursa (job #994624) | Cod sursa (job #2759956)
#include <bits/stdc++.h>
#define f double
#define x first
#define y second
#define pi 3.14159
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair<f,f> sj;
f orietation(pair<f,f> a, pair<f,f> b, pair<f,f> c)
{
return (b.y-a.y)*(c.x-b.x)-(c.y-b.y)*(b.x-a.x);
}
bool cmp(const pair<f,f> &a, const pair<f,f> &b)
{
return orietation(sj,a,b)<0;
}
vector<pair<f,f> > infas(vector<pair<f,f> > v)
{
sort(v.begin(),v.end(),cmp);
vector<pair<f,f> > ans;
ans.push_back(sj); ans.push_back(v[0]);
for(int i=1;i<v.size();i++)
{
pair<f,f> p1=ans[ans.size()-2],p2=ans[ans.size()-1];
while(ans.size()>1&&orietation(p1,p2,v[i])>0)
{
ans.pop_back();
p2=p1;
if(ans.size()>1) p1=ans[ans.size()-2];
}
ans.push_back(v[i]);
}
return ans;
}
int main()
{
int n;
vector<pair<f,f> > pts;
int sjpos;
in>>n;
for(int i=0;i<n;i++)
{
pair<f,f> pt;
in>>pt.x>>pt.y;
pts.push_back(pt);
if(pt.x<sj.x||i==0) {sj=pt; sjpos=i;}
if(pt.x==sj.x&&pt.y<sj.y) {sj=pt; sjpos=i;}
}
for(int i=0;i<n;i++)
{
if(i>sjpos) pts[i-1]=pts[i];
}
pts.pop_back();
pts=infas(pts);
out<<pts.size()<<'\n';
for(int i=0;i<pts.size();i++)
{
out<<fixed<<setprecision(6)<<pts[i].x<<' '<<pts[i].y<<'\n';
}
return 0;
}