Cod sursa(job #680604)

Utilizator Daniel30daniel Daniel30 Data 15 februarie 2012 19:33:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct punct{double x,y;} aux;
int n,x,y;
vector<punct> p,st;
bool cmp(const punct &a, const punct &b)
{if(a.x<b.x) return true;
 if(a.x>b.x) return false;
 if(a.y<b.y) return true;
 if(a.y>b.y) return false;
 return true;
}

bool semn(const punct &a,const punct &b, const punct &c)
{double A=b.x*c.y+c.x*a.y+a.x*b.y;
 double B=-a.x*c.y-b.x*a.y-c.x*b.y;
 return (A+B)<0.0;
}

int main()
{freopen("infasuratoare.in","rt",stdin);
 freopen("infasuratoare.out","wt",stdout);
 for(scanf("%d",&n); n; --n) scanf("%lf%lf",&x,&y),p.push_back((punct){x,y});
 sort(p.begin(),p.end(),cmp);
 st.push_back(p[0]); st.push_back(p[1]);
 for(unsigned int i=2; i<p.size(); ++i) 
	{for(;st.size()>1 && semn(st[st.size()-2],st[st.size()-1],p[i]); st.pop_back());
	 st.push_back(p[i]);
	}
 for(unsigned int i=p.size(); i>0 ; --i) 
	{for(;st.size()>1 && semn(st[st.size()-2],st[st.size()-1],p[i]); st.pop_back());
	 st.push_back(p[i]);
	}
 st.pop_back(); 
 printf("%d\n",st.size());
 for(unsigned int i=0; i<st.size(); ++i)
	 printf("%0.6lf %0.6lf\n",st[i].x,st[i].y);
 return 0;
}