Pagini recente » Cod sursa (job #3125064) | Cod sursa (job #353679) | Autentificare | Cod sursa (job #658892) | Cod sursa (job #2193556)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x,y;
double px=1000000001;
double py=1000000001;
vector<pair<double,double> >elem,rez;
bool cmp(pair<double,double>a,pair<double,double>b)
{
double unga,ungb;
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)));
if(py<b.second)
ungb=1.0*(b.first-px)/(1.0*sqrt(1.0*(b.first-px)*(b.first-px)+1.0*(b.second-py)*(b.second-py)));
else
ungb=1+1.0*(py-b.second)/(1.0*sqrt(1.0*(b.first-px)*(b.first-px)+1.0*(py-b.second)*(py-b.second)));
if(unga==ungb)
return a.first<b.first;
return unga<ungb;
}
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.erase(rez.end());
}
h++;
rez.push_back({elem[i].first,elem[i].second});
}
h+=2;
fout<<h<<"\n";
for(int i=0;i<h;i++)
fout<<rez[i].second<<" "<<rez[i].first<<"\n";
}
int main()
{
fin>>n;
fout<<fixed;
fout<<setprecision(12);
int ind=0;
for(int i=0;i<n;i++)
{
fin>>y>>x;
elem.push_back({x,y});
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());
sort(elem.begin(),elem.end(),cmp);
infasuratoare();
return 0;
}