Pagini recente » Cod sursa (job #888566) | Cod sursa (job #129880) | Cod sursa (job #2760259) | Cod sursa (job #2282972) | Cod sursa (job #2759951)
#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={-1,-1};
f angleTo( pair<f,f> o, pair<f,f> p)
{
return atan2(p.y-o.y,p.x-o.x);
}
bool cmp(const pair<f,f> &a, const pair<f,f> &b)
{
return (angleTo(sj,a)<angleTo(sj,b))||(angleTo(sj,a)==angleTo(sj,b)&&a.x<b.x);
}
vector<pair<f,f> > infas(vector<pair<f,f> > v)
{
sort(v.begin(),v.end(),cmp);
vector<pair<f,f> > ans;
//cout<<angleTo(sj,{2,0})/pi*180<<'\n';
// cout<<sj.x<<','<<sj.y<<'\n';
//for(int i=0;i<v.size();i++)
// cout<<v[i].x<<','<<v[i].y<<' ';
//cout<<'\n';
ans.push_back(sj); ans.push_back(v[0]);
for(int i=1;i<v.size();i++)
{
pair<f,f> p1=ans[ans.size()-1],p2=ans[ans.size()-2];
while(ans.size()>1&&angleTo(p1,p2)>angleTo(p2,v[i]))
{
//cout<<angleTo(p1,p2)<<' '<<angleTo(p2,v[i])<<' '<<p1.x<<','<<p1.y<<' '<<p2.x<<','<<p2.y<<' '<<v[i].x<<','<<v[i].y<<'\n';
ans.pop_back();
p1=p2;
if(ans.size()>1) p2=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;
}