Pagini recente » Cod sursa (job #1082524) | Cod sursa (job #1499488) | iconcurs2 | Cod sursa (job #1029519) | Cod sursa (job #2535633)
#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;
bool bye = false;
};
int n;
double det(vec2 a, vec2 b, vec2 c){
return (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);
}
bool cmp(const vec2 &lhs, const vec2 &rhs){
return lhs.x < rhs.x;
}
vector<vec2> wa;
vector<int> ans;
bool chec(int a){
int s = ans.size();
if(s <= 1){
return true;
}else{
return det(wa[ans[s-2]], wa[ans[s-1]], wa[a]) >= 0;
}
}
void yeet(){
for(int i = 0; i < n; ++i){
while(!chec(i)){
wa[ans.back()].bye = false;
ans.pop_back();
}
wa[i].bye = true;
ans.push_back(i);
}
for(int i = n-1; i >= 0; --i){
if(!wa[i].bye){
while(!chec(i)){
wa[ans.back()].bye = false;
ans.pop_back();
}
wa[i].bye = true;
ans.push_back(i);
}
}
}
int main(){
fin >> n;
for(int i = 0; i < n; ++i){
vec2 a;
fin >> a.x >> a.y;
wa.push_back(a);
}
sort(wa.begin(), wa.end(), cmp);
yeet();
fout << fixed << setprecision(6);
fout << ans.size() << "\n";
for(auto a : ans){
vec2 b = wa[a];
fout << b.x << " " << b.y << "\n";
}
return 0;
}