Pagini recente » Cod sursa (job #1351918) | Cod sursa (job #873372) | Cod sursa (job #2028858) | Cod sursa (job #2769780) | Cod sursa (job #1473814)
#include <bits/stdc++.h>
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
using namespace std;
typedef pair<double, double> Pair;
#define x first
#define y second
#define NMAX 120005
#define pb push_back
#define pp pop_back
Pair P[NMAX];
vector<int> up;
vector<int> down;
int n;
int det(int i1, int i2, int i3){
int dx1 = P[i2].x-P[i1].x,
dx2 = P[i3].x-P[i1].x,
dy1 = P[i2].y-P[i1].y,
dy2 = P[i3].y-P[i1].y;
return (1LL*dx1*dy2)-(1LL*dy1*dx2);
}
void insertUp(int i){
while(up.size()>=2 && det(up[up.size()-2], up[up.size()-1], i)>0)
up.pp();
up.pb(i);
}
void insertDown(int i){
while(down.size()>=2 && det(down[down.size()-2], down[down.size()-1], i)<0)
down.pp();
down.pb(i);
}
void hull(){
int i;
for(i=1;i<=n;i++){
insertUp(i);
insertDown(i);
}
fout<<down.size()-2+up.size()<<'\n';
for(i=1;i<down.size();i++)
fout<<fixed<<setprecision(6)<<P[down[i]].x<<" "<<P[down[i]].y<<'\n';
for(i=up.size()-2; i; i--)
fout<<fixed<<setprecision(6)<<P[up[i]].x<<" "<<P[up[i]].y<<'\n';
fout<<fixed<<setprecision(6)<<P[down.front()].x<<" "<<P[down.front()].y;
}
int main() {
fin>>n;
int i;
for(i=1;i<=n;i++)
fin>>P[i].x>>P[i].y;
sort(P+1,P+n+1,[](Pair a, Pair b){
return a.x<b.x || (a.x==b.x && a.y<b.y);
});
hull();
return 0;
}