Pagini recente » Cod sursa (job #2440957) | Cod sursa (job #1611032) | Cod sursa (job #2352989) | Cod sursa (job #278489) | Cod sursa (job #3327258)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x,y;
}p[120005];
int cresc(point a,point b)
{
if(a.x<b.x)
return 1;
else if(a.x==b.x)
{
if(a.y<b.y)
return 1;
}
return 0;
}
int decresc(point a,point b)
{
if(a.x>b.x)
return 1;
else if(a.x==b.x)
{
if(a.y>b.y)
return 1;
}
return 0;
}
deque <pair<double,double>> to_dr;
deque <pair<double,double>> to_st;
int n;
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1,cresc);
to_st.push_front(make_pair(p[1].x,p[1].y));
to_st.push_front(make_pair(p[2].x,p[2].y));
for(int i=3;i<=n;i++)
{
double det=0;
do{
double xb=to_st.front().first;
double yb=to_st.front().second;
to_st.pop_front();
double xa=to_st.front().first;
double ya=to_st.front().second;
to_st.push_front(make_pair(xb,yb));
double xc=p[i].x;
double yc=p[i].y;
det=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
//cout<<xa<<" "<<ya<<endl<<xb<<" "<<yb<<endl<<xc<<" "<<yc<<endl<<det<<endl<<endl;
if(det==0)
{
to_st.pop_front();
}
else if (det<0)
{
to_st.pop_front();
}
}while(det<0 && to_st.size()>1);
to_st.push_front(make_pair(p[i].x,p[i].y));
}
sort(p+1,p+n+1,decresc);
to_dr.push_front(make_pair(p[1].x,p[1].y));
to_dr.push_front(make_pair(p[2].x,p[2].y));
for(int i=3;i<=n;i++)
{
double det=0;
do{
double xb=to_dr.front().first;
double yb=to_dr.front().second;
to_dr.pop_front();
double xa=to_dr.front().first;
double ya=to_dr.front().second;
to_dr.push_front(make_pair(xb,yb));
double xc=p[i].x;
double yc=p[i].y;
det=xa*yb+xb*yc+xc*ya-ya*xb-yb*xc-yc*xa;
//cout<<xa<<" "<<ya<<endl<<xb<<" "<<yb<<endl<<xc<<" "<<yc<<endl<<det<<endl<<endl;
if(det==0)
{
to_dr.pop_front();
}
else if(det<0)
{
to_dr.pop_front();
}
}while(det<0 && to_dr.size()>1);
to_dr.push_front(make_pair(p[i].x,p[i].y));
}
fout<<to_dr.size()+to_st.size()-2<<"\n";
while(!to_dr.empty())
{
fout<<to_dr.back().first<<" "<<to_dr.back().second<<"\n";
to_dr.pop_back();
}
to_st.pop_back();
to_st.pop_front();
while(!to_st.empty())
{
fout<<to_st.back().first<<" "<<to_st.back().second<<"\n";
to_st.pop_back();
}
return 0;
}