Pagini recente » Cod sursa (job #2392351) | Cod sursa (job #489392) | Cod sursa (job #1739905) | Cod sursa (job #1154481) | Cod sursa (job #897470)
Cod sursa(job #897470)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define DN 120005
#define x first
#define y second
#define per pair<double,double>
using namespace std;
per p[DN];
stack< per > st;
double ccw( per p1,per p2,per p3)
{
return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y) *( p3.x - p1.x );
}
int cmp(per p1,per p2)
{
return ccw(p[1],p1,p2) < 0;
}
int main()
{
int n;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
int poz=1;
for(int i=1;i<=n;++i)
{
f>>p[i].x>>p[i].y;
if(p[i]<p[poz])
poz=i;
}
swap(p[1],p[poz]);
sort(p+2,p+n+1,cmp);
st.push(p[1]);
st.push(p[2]);
for(int i=3;i<=n;++i)
{
bool ok = true;
while(st.size()>=2 && ok)
{
per first=st.top();
st.pop();
if( ccw(st.top(),first,p[i]) <= 0 )
st.push(first),ok=false;// il punem la loc
}
st.push(p[i]);
}
g<<fixed<<st.size()<<"\n";
while(st.size())
{
g<<setprecision(6)<<st.top().x<<" "<<st.top().y<<"\n";
st.pop();
}
return 0;
}