Pagini recente » Monitorul de evaluare | Cod sursa (job #2069252) | Cod sursa (job #1154310) | Cod sursa (job #627329) | Cod sursa (job #2659567)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct vec2{
double x, y;
};
double det(vec2 v1, vec2 v2, vec2 v3){
return (v2.x-v1.x)*(v3.y-v1.y)
-(v3.x-v1.x)*(v2.y-v1.y);
}
int n;
vec2 vex[120041];
bool vi[120041];
bool cmp(const vec2 &v1, const vec2 &v2){
if(v1.x != v2.x) return v1.x < v2.x;
else return v1.y < v2.y;
}
void read(){
fin >> n;
for(int i = 0; i < n; ++i){
vec2 &v = vex[i];
fin >> v.x >> v.y;
}
}
struct yip{
vec2 v;
int p;
};
yip makeyip(int i){
return {vex[i],i};
}
vector<yip> hulio;
bool isgood(vec2 v){
int s = hulio.size();
return det(hulio[s-2].v, hulio[s-1].v, v)>0;
}
void solve(){
sort(vex, vex+n, cmp);
hulio.push_back(makeyip(0));
vi[0] = true;
hulio.push_back(makeyip(1));
vi[1] = true;
for(int i = 2; i < n; ++i){
while(hulio.size() >= 2 && !isgood(vex[i])){
vi[hulio.back().p] = false;
hulio.pop_back();
}
hulio.push_back(makeyip(i));
vi[i] = true;
}
for(int i = n-1; i >= 0; --i){
if(vi[i])continue;
while(hulio.size() >= 2 && !isgood(vex[i])){
vi[hulio.back().p] = false;
hulio.pop_back();
}
hulio.push_back(makeyip(i));
vi[i] = true;
}
}
void write(){
fout << hulio.size() << "\n";
fout << fixed << setprecision(6);
for(auto &yi : hulio){
fout << yi.v.x << " " << yi.v.y << "\n";
}
}
int main(){
// ios_base::sync_with_stdio(false);
read();
solve();
write();
return 0;
}