Pagini recente » Cod sursa (job #2895732) | Cod sursa (job #1728132) | Cod sursa (job #2114790) | Cod sursa (job #1129145) | Cod sursa (job #377346)
Cod sursa(job #377346)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair <double,double> p;
int n;
vector <p> a;
class stack
{
public:
vector <p> st;
void pb(p x)
{
st.push_back(x);
}
void pop()
{
st.pop_back();
}
p last()
{
return st.back();
}
p last2()
{
return st[st.size()-2];
}
void Print()
{
printf("%d\n",(int)st.size());
for(int i=0;i<(int)st.size();i++)
printf("%lf %lf\n",st[i].first,st[i].second);
}
};
bool cmp(p x,p y)
{
return (y.first-a.begin()->first)*(x.second-a.begin()->second)<(x.first-a.begin()->first)*(y.second-a.begin()->second);
}
double prod(p x,p y,p z)
{
return (z.first-x.first)*(y.second-x.second)-(y.first-x.first)*(z.second-x.second);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
p x;
scanf("%lf%lf",&x.first,&x.second);
a.push_back(x);
}
vector <p> ::iterator it =a.begin()+1,min=a.begin();
for(;it!=a.end();it++)
if(it->first<min->first||it->first==min->first&&it->second<min->second)
min=it;
swap(*a.begin(),*min);
stable_sort(a.begin()+1,a.end(),cmp);
stack st;
st.pb(*a.begin());st.pb(*(a.begin()+1));st.pb(*(a.begin()+2));
it=a.begin()+3;
while(it!=a.end())
{
while(prod(st.last2(),st.last(),*it)>=0)
st.pop();
st.pb(*it++);
}
st.Print();
return 0;
}