Pagini recente » Cod sursa (job #1245092) | Cod sursa (job #2363526) | Cod sursa (job #1510072) | Cod sursa (job #2502154) | Cod sursa (job #2470482)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct chestie{
double x,y,r;
bool ok;
}p[120120];
int N, ixmn,xmin,k,ymx;
vector <chestie> v;
inline void scan();
inline void print();
bool side(chestie A, chestie B, chestie C);
bool comp(const chestie &A, const chestie &B);
int main()
{
scan();
p[ixmn].ok=1;
for(int i=1; i<=N; ++i) //panta pozitiva
{
if(p[i].x!=p[ixmn].x)
p[i].r=(p[i].y-p[ixmn].y)/(p[i].x-p[ixmn].x);
else p[i].r=0;
}
sort(p+1, p+N+1, comp);
p[2].ok=1;k=1;
v.push_back(p[1]);
v.push_back(p[2]);
for(int i=3; i<=N; ++i)
if(!side(v[k-1],v[k],p[i]))
{
v.push_back(p[i]);
k++;
}
else{
while(k>1 && side(v[k-1],v[k],p[i]))
k--;
v[++k]=p[i];
}
print();
return 0;
}
inline void scan(){
cin>>N;
for(int i=1; i<=N; ++i)
{
cin>>p[i].x>>p[i].y;
if( (p[i].x<xmin&& (p[i].x==xmin || p[i].y>ymx) )|| ixmn==0)
ixmn=i, xmin=p[i].x, ymx=p[i].y;
}
}
inline void print(){
cout<<k+1<<'\n';
for(int i=0; i<=k; ++i)
{
cout<<fixed;
cout<<setprecision(6)<<v[i].x<<' ';
cout<<setprecision(6)<<v[i].y<<'\n';
}
}
bool comp(const chestie &A, const chestie &B)
{
return (A.ok>B.ok ||(A.r<B.r||(A.r==B.r && (A.y>B.y|| (A.y==B.y && A.x<B.x)))));
}
bool side(chestie A, chestie B, chestie C)
{
double ar=(A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.x*C.y-B.x*A.y);
return (ar<0);
}