Pagini recente » Cod sursa (job #3131013) | Cod sursa (job #1160602) | Cod sursa (job #264396) | Cod sursa (job #658770) | Cod sursa (job #2193578)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
long double x,y;
long double px=1000000001;
long double py=1000000001;
struct elements
{
long double first,second,third;
};
vector<pair<long double,long double> >rez;
vector<elements>elem;
long double make_unghi(elements a)
{
long double unga;
if(py<a.second)
unga=1.0*(a.first-px)/(1.0*sqrt(1.0*(a.first-px)*(a.first-px)+1.0*(a.second-py)*(a.second-py)));
else
unga=1+1.0*(py-a.second)/(1.0*sqrt(1.0*(a.first-px)*(a.first-px)+1.0*(py-a.second)*(py-a.second)));
return unga;
}
bool cmp(elements a,elements b)
{
if(a.third==b.third)
return a.first<b.first;
return a.third<b.third;
}
void infasuratoare()
{
rez.push_back({px,py});
rez.push_back({elem[0].first,elem[0].second});
int k=-1;
int h=0;
if(py<elem[0].second)
k=1;
for(int i=1;i<n-1;i++)
{
while(k*(elem[i].first*(rez[h+1].second-rez[h].second)+rez[h+1].first*(rez[h].second-elem[i].second)+rez[h].first*(elem[i].second-rez[h+1].second))<=0)
{
h--;
rez.pop_back();
}
h++;
rez.push_back({elem[i].first,elem[i].second});
}
h+=2;
fout<<fixed;
fout<<setprecision(6);
fout<<h<<"\n";
for(int i=0;i<h;i++)
fout<<rez[i].second<<" "<<rez[i].first<<"\n";
}
int main()
{
fin>>n;
int ind=0;
for(int i=0;i<n;i++)
{
fin>>y>>x;
elem.push_back({x,y,0});
if(x<px)
{
px=x;
py=y;
ind=i;
continue;
}
if(x==px && py>y)
{
px=x;
py=y;
ind=i;
continue;
}
}
elem.erase(ind+elem.begin());
for(int i=0;i<n-1;i++)
elem[i].third=make_unghi(elem[i]);
sort(elem.begin(),elem.end(),cmp);
infasuratoare();
return 0;
}