Pagini recente » Cod sursa (job #1045885) | Cod sursa (job #812701) | Cod sursa (job #2723060) | Cod sursa (job #3138221) | Cod sursa (job #3207367)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define dd double
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct coord{
dd x, y;
};
int n;
vector <coord> v;
vector <coord> stak;
coord pct0 = {1e9 + 5, 0};
int poz;
int cadran(coord pct){
if(pct.y >= 0){
if(pct.x >= 0)
return 1;
return 2;
}
if(pct.x < 0)
return 3;
return 4;
}
dd determinant(dd x1, dd y1, dd x2, dd y2, dd x3, dd y3){
return x1 * (y2-y3) + x2 * (y3-y1) + x3 * (y1-y2);
}
bool cmp(coord a, coord b){
int cadran1 = cadran(a), cadran2 = cadran(b);
if(cadran1 != cadran2)
return(cadran1 < cadran2);
else{
double det = determinant(pct0.x, pct0.y,a.x,a.y,b.x,b.y);
if(det == 0)
return (a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y);
return det > 0;
}
}
void solve(){
for(int i = 0; i < n; i++){
if(v[i].x < pct0.x or (v[i].x == pct0.x and v[i].y < pct0.y)){
pct0 = v[i];
poz = i;
}
}
swap(v[0], v[poz]);
sort(v.begin() + 1, v.end(), cmp);
// for(auto vec:v)
// cout << vec.x << ' ' << vec.y << '\n';
stak.push_back(v[0]);
stak.push_back(v[1]);
int len = 2;
for(int i = 2; i < v.size(); i++) {
if (stak.size() >= 2 and
determinant(stak[len - 2].x, stak[len - 2].y, stak[len - 1].x, stak[len - 1].y, v[i].x, v[i].y) < 0){
stak.pop_back();
len--;
}
stak.push_back(v[i]);
len++;
}
}
int main()
{
cin >> n;
cout << fixed << setprecision(13);
for(int i = 0; i < n; i++){
double x, y;
cin >> x >> y;
v.push_back({x, y});
}
solve();
cout << stak.size() << '\n';
for(auto &i : stak)
cout << i.x << ' ' << i.y << '\n';
// while(!stak.empty()){
// cout << stak.top().x << ' ' << st.top().y << '\n';
// st.pop();
// }
// for(auto unghi:v)
// cout << unghi.x << ' ' << unghi.y << '\n';
return 0;
}