Pagini recente » Cod sursa (job #2614536) | Cod sursa (job #1914253) | Cod sursa (job #2670685) | Cod sursa (job #320540) | Cod sursa (job #889300)
Cod sursa(job #889300)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define MAXN 120005
#define INF 2000000000
#define EPS 0.000000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
double x,y,up;};
int n,mni;
double mnx=INF,mny;
punct p[MAXN],a,b,c;
vector<punct> st;
bool Comp(punct p1,punct p2){
return p1.up<p2.up;}
double ABS(double m){
return m>0?m:(-m);}
int main()
{
int i;
f>>n;
for(i=1;i<=n;i++){
f>>p[i].x>>p[i].y;
if(ABS(p[i].x-mnx)<EPS&&p[i].y<mny){
mny=p[i].y;
mni=i;
continue;}
if(p[i].x<mnx){
mnx=p[i].x;
mny=p[i].y;
mni=i;}}
for(i=1;i<=n;i++){
if(p[i].x==mnx){
if(mni==i)
p[i].up=-INF;
else
p[i].up=INF;
continue;}
p[i].up=(p[i].y-mny)/(p[i].x-mnx);}
sort(p+1,p+n+1,Comp);
st.push_back(p[1]);
st.push_back(p[2]);
for(i=3;i<=n;i++){
b=st[st.size()-1];
a=st[st.size()-2];
c=p[i];
while(c.x*(a.y-b.y)+c.y*(b.x-a.x)+a.x*b.y-a.y*b.x<EPS){
b=a;
st.pop_back();
a=st[st.size()-2];}
st.push_back(c);}
g<<st.size()<<'\n'<<fixed<<setprecision(12);
for(i=0;i<st.size();i++)
g<<st[i].x<<' '<<st[i].y<<'\n';
f.close();
g.close();
return 0;
}