Pagini recente » Cod sursa (job #2824318) | Cod sursa (job #914154) | Cod sursa (job #2637244) | Cod sursa (job #2720491) | Cod sursa (job #3250374)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#define mkp make_pair
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
long double x,y;
long double uOX;
} p[120001];
int n,i;
vector<pair<punct,bool>>conv;
punct pjosmax= {1e9,1e9,0};
int indpfirst;
long double lvec(punct p1,punct p2)
{
int dif1 = p1.x-p2.x;
int dif2 = p1.y-p2.y;
return sqrt(dif1*dif1 + dif2*dif2);
}
long double calcunghi(punct p1,punct p2)
{
long double lungp1= lvec(p1,{0,0,0}),lungp2=1,lungfin = lvec(p1,p2);
return (lungfin*lungfin - lungp1*lungp1 - lungp2*lungp2) / (-2*lungp1*lungp2);
}
bool cmp(punct a,punct b)
{
if(a.uOX != b.uOX)
return a.uOX < b.uOX;
return a.x < b.x;
}
long double arie(punct p1,punct p2,punct p3)
{
return (long double)(p1.x*p2.y + p1.y*p3.x + p2.x*p3.y - p1.x*p3.y - p1.y*p2.x - p2.y*p3.x)/2;
}
int main()
{
cin>>n;
for(i=1; i<=n; i++)
{
cin>>p[i].x>>p[i].y;
if(p[i].y < pjosmax.y)
{
pjosmax = p[i];
indpfirst = i;
}
else if(p[i].y == pjosmax.y&&pjosmax.x>p[i].x)
{
pjosmax = p[i];
indpfirst = i;
}
}
for(i=1; i<=n; i++)
{
if(i == indpfirst)
continue;
punct newpct = {p[i].x-pjosmax.x,p[i].y-pjosmax.y,0};
long double cosu = calcunghi(newpct,{1,0,0});
p[i].uOX = acos(cosu);
}
sort(p+1,p+n+1,cmp);
conv.push_back(mkp(pjosmax,1));
n++;
p[n] = pjosmax;
for(i=2; i<=n; i++)
{
if(conv[conv.size()-1].second)
{
if(conv[conv.size()-1].first.y<p[i].y)
conv.push_back(mkp(p[i],1));
else
{
conv.push_back(mkp(p[i],0));
}
}
else
{
if(conv[conv.size()-1].first.y>p[i].y)
conv.push_back(mkp(p[i],0));
else
{
while(conv[conv.size()-1].first.y<=p[i].y&&conv[conv.size()-1].second!=1)
conv.pop_back();
if(conv[conv.size()-1].first.y<p[i].y)
conv.push_back(mkp(p[i],1));
else
conv.push_back(mkp(p[i],0));
}
}
}
cout<<conv.size()-1<<'\n';
for(int h=0; h<conv.size()-1; h++)
{
cout<<fixed<<setprecision(6)<<conv[h].first.x<<" "<<conv[h].first.y<<'\n';
}
return 0;
}