Pagini recente » Cod sursa (job #2904984) | Cod sursa (job #2630143) | Cod sursa (job #2279314) | Cod sursa (job #1725872) | Cod sursa (job #3206891)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Radu{
double x, y;
};
vector <Radu> v;
int n;
double mina = 1e9, minb = 1e9;
int cadran(double x, double y) {
if( x > 0 && y >= 0 )
return 1;
if( x >= 0 && y < 0 )
return 4;
if( y > 0 && x <= 0 )
return 2;
return 3;
}
double det( double x1, double y1, double x2, double y2, double x3, double y3) {
return x1 * (y2- y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
}
int cmp(const Radu &a, const Radu &b ) {
int c1 = cadran(a.x, a.y);
int c2 = cadran(b.x, b.y);
// if( c1 != c2 )
// return c1 < c2;
double d = det( mina, minb, a.x, a.y, b.x, b.y);
// if( d != 0 )
return d > 0;
// return a.x * a.x + a.y * a.y > b.x * b.x + b.y * b.y;
}
bool convex( Radu a, Radu b, Radu c ){
return det( a.x, a.y, b.x, b.y, c.x, c.y ) > 0;
}
int main() {
in >> n;
int ind;
for( int i = 0; i < n; i++ ){
double a, b;
in >> a >> b;
v.push_back({a,b});
if( b < minb || ( b == minb && a < mina ) ){
minb = b;
mina = a;
ind = i;
}
}
swap(v[0], v[ind]);
sort(v.begin()+1, v.end(), cmp);
// for( auto i : v )
// out << fixed << setprecision(6) << i.x << " " << i.y << "\n";
// out << "\n";
v.push_back(v[0]);
vector <Radu> q;
q.push_back(v[0]);
for( int i = 1; i < v.size(); i++ ){
Radu punct = v[i];
if( q.size() == 1 )
q.push_back(punct);
else{
int len = q.size();
while( q.size() > 1 && !convex(q[len-2], q[len-1], punct) ){
// cout << q[len-2].x << " " << q[len-2].y << " " << q[len-1].x << " " << q[len-1].y << " " << punct.x << " " << punct.y << "\n";
q.pop_back();
len--;
}
q.push_back(punct);
}
}
q.pop_back();
out << q.size() << "\n";
for( auto i : q )
out << fixed << setprecision(6) << i.x << " " << i.y << "\n";
return 0;
}