Pagini recente » Cod sursa (job #1395300) | Cod sursa (job #955441) | Cod sursa (job #703582) | Cod sursa (job #469104) | Cod sursa (job #3276588)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream gout("infasuratoare.out");
struct pct
{
double x,y;
};
int orientation(const pct&a,const pct&b,const pct&c)
{
double val=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
if(!val)return 0;
if(val>0)return 1;
else return 2;
}
double dist(const pct&p1,const pct&p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
bool compare(const pct &p0, const pct &p1, const pct &p2)
{
int o=orientation(p0,p1,p2);
if(o==0)return dist(p0,p1)<dist(p0,p2);
return o==2;
}
int main()
{
int n;
fin>>n;
vector<pct>v(n);
for(int i=0; i<n; ++i)fin>>v[i].x>>v[i].y;
v.erase(unique(v.begin(), v.end(), [](const pct &a, const pct &b)
{
return a.x == b.x && a.y == b.y;
}), v.end());
pct p0=*min_element(v.begin(),v.end(),[](const pct &a, const pct &b)
{
return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
});
sort(v.begin(),v.end(),[&p0](const pct &p1,const pct &p2)
{
return compare(p0,p1,p2);
});
vector<pct>ans;
ans.push_back(v[0]);
ans.push_back(v[1]);
ans.push_back(v[2]);
for(int i=3; i<v.size(); ++i)
{
while(ans.size()>1&&
orientation(ans[ans.size()-2],ans.back(),v[i])!=2)ans.pop_back();
ans.push_back(v[i]);
}
p0=ans.front();
sort(ans.begin(),ans.end(),[&p0](const pct&a,const pct&b)->bool
{
return atan2(a.y-p0.y,a.x-p0.x)<atan2(b.y-p0.y,b.x-p0.x);
});
gout<<ans.size()<<'\n';
while(!ans.empty())
{
gout<<fixed<<setprecision(12)<<ans.back().x<<' '<<ans.back().y<<'\n';
ans.pop_back();
}
return 0;
}