Pagini recente » Cod sursa (job #2574922) | Cod sursa (job #2518483) | Cod sursa (job #1820668) | Cod sursa (job #2598572) | Cod sursa (job #3271161)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <deque>
//#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using db = long double;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
db x, y, rad; // radiani
};
db det(punct a, punct b, punct c){
a.x -= c.x;
b.x -= c.x;
a.y -= c.y;
b.y -= c.y;
return a.x * b.y - a.y * b.x;
}
bool cmp(punct a, punct b){
if(a.rad != b.rad) return a.rad > b.rad;
else if(a.x != b.x) return a.x > b.x;
else return a.y > b.y;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; in >> n;
punct v[n];
db x0 = 0, y0 = 0;
for(int i = 0; i < n; i++){
in >> v[i].x >> v[i].y;
x0 += v[i].x;
y0 += v[i].y;
}
x0 /= n;
y0 /= n;
// cout << "x0 = " << x0 << " y0 = " << y0 << '\n';
for(int i = 0; i < n; i++){
v[i].rad = atan2(v[i].y - y0, v[i].x - x0);
// cout << "i = " << i << " v = " << v[i].x << " " << v[i].y << " rad = " << v[i].rad << '\n';
}
sort(v + 0, v + n, cmp);
// cout << "v : \n";
// for(int i = 0; i < n; i++){
// cout << v[i].x << " " << v[i].y << '\n';
// }
deque< punct > sol;
for(int i = 0; i < n; i++){
// cout << "Suntem la ( " << v[i].x << " , " << v[i].y << " )\n";
while(sol.size() >= 2){
punct a = sol[ sol.size() - 2 ];
punct b = sol[ sol.size() - 1 ];
if( det( a, b, v[i] ) > 0 ){
// cout << " -- > Eliminam " << b.x << " , " << b.y << '\n';
sol.pop_back();
}else break;
}
sol.push_back(v[i]);
}
// out << sol.size() << '\n';
// for(int i = 0; i < sol.size(); i++){
// out << fixed << setprecision(6) << sol[i].x << " " << sol[i].y << '\n';
// }
while(sol.size() >= 3){
punct a = sol[ sol.size() - 2 ];
punct b = sol[ sol.size() - 1 ];
if( det( sol[0], a, b ) > 0 ){
sol.pop_back();
}else break;
}
while(sol.size() >= 3){
punct a = sol[ sol.size() - 1 ];
punct b = sol[ 0 ];
if( det( sol[0], sol[1], sol[sol.size() - 1] ) > 0 ){
sol.pop_front();
}else break;
}
reverse(sol.begin(), sol.end());
out << sol.size() << '\n';
for(int i = 0; i < sol.size(); i++){
out << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << '\n';
}
return 0;
}