Pagini recente » Borderou de evaluare (job #1570210) | Borderou de evaluare (job #2456752) | Borderou de evaluare (job #1079968) | Cod sursa (job #195077) | Cod sursa (job #3270905)
#include <iostream>
#include<fstream>
#include<algorithm>
#include<deque>
#include<iomanip>
using namespace std;ifstream fin("infasuratoare.in");ofstream fout("infasuratoare.out");struct qer{double x,y;};int n,idx,i;qer v[120001],p0;double mx=-1000000001;deque<qer>q;
double arie(qer p0,qer p1,qer p2){p1.x-=p0.x;p1.y-=p0.y;p2.x-=p0.x;p2.y-=p0.y;
return p1.x*p2.y-p2.x*p1.y;}
double dist(qer p1){return (p1.x-p0.x)*(p1.x-p0.x)+(p1.y-p0.y)*(p1.y-p0.y);}
bool comp(qer p1,qer p2){mx=arie(p0,p1,p2);if(mx==0)return dist(p1)<dist(p2);
return mx<0;
}
int main()
{fin>>n;for(i=1;i<=n;i++){fin>>v[i].x>>v[i].y;if(v[i].x>mx||v[i].x==mx&&v[i].y<v[idx].y){idx=i;mx=v[i].x;}}p0=v[idx];sort(v+1,v+n+1,comp);
q.push_back(v[1]);for(i=2;i<=n;i++){while(q.size()>1&&arie(q[1],q[0],v[i])>0)q.pop_front();q.push_front(v[i]);}
fout<<q.size()<<'\n';while(!q.empty())fout<<fixed<<setprecision(12)<<q.front().x<<" "<<q.front().y<<'\n',q.pop_front();
return 0;
}