Pagini recente » Cod sursa (job #600295) | Cod sursa (job #1675094) | Cod sursa (job #2537921) | Cod sursa (job #412709) | Cod sursa (job #2537734)
#include <bits/stdc++.h>
#define NMAX (int)(2e5+4)
#define pb emplace_back
#define ft first
#define sd second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair <int, int> pairINT;
typedef long long ll;
struct point{
double x,y;
bool operator<(const point& oth)const{
return (make_pair(x, y) < make_pair(oth.x, oth.y));
}
};
point p[NMAX];
int n;
vector <int> stk;
bool TrigoOrder(point,point,point);
inline bool cond(point&,point&);
int main(){
fin>>n;
double x,y;
for(int i=0;i<n;++i){
fin>>x>>y;
p[i]={x, y};
if(p[i] < p[0])
swap(p[i], p[0]);
}
//p[0] tine minimul
sort(p+1,p+n,cond);
stk.push_back(0);
stk.push_back(1);
for(int i=2;i<n;++i){
while(!TrigoOrder(p[stk[stk.size()-2]], p[stk.back()], p[i]))
stk.pop_back();
stk.push_back(i);
}
fout<<fixed<<setprecision(12);
fout<<stk.size()<<'\n';
for(auto it:stk)
fout<<p[it].x<<' '<<p[it].y<<'\n';
return 0;
}
inline bool cond(point& A,point& B){
return TrigoOrder(p[0], A, B);
}
bool TrigoOrder(point A,point B,point C){
return ((C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x)) > 0.0;
}