Pagini recente » Cod sursa (job #1598180) | Cod sursa (job #2526406) | Cod sursa (job #2304143) | Cod sursa (job #2756286) | Cod sursa (job #2730771)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define ll long long
const int NMAX = 200000;
const double eps = 1.0e-14;
struct point
{
double x, y;
};
point v[NMAX+5], low;
inline double cp(point p1, point p2, point p3)
{
return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
}
inline int ccw(point p1, point p2, point p3){
double vcp = cp(p1, p2, p3);
if(fabs(vcp) < eps)
return 0;
if(vcp>=eps)
return 1;
else return -1;
}
int h[NMAX+5];
bool cmp(point p1, point p2)
{
int sccw = ccw(low, p1, p2);
if(sccw > 0)
return 1;
else return 0;
}
inline double dist(point p1, point p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
vector<point>hull;
double normal(vector<point> &a, int p1, int p2) {
int p11 = (p1 + 1 + a.size()) % a.size();
double A = a[p1].y - a[p11].y;
double B = a[p11].x - a[p1].x;
double C = -A * a[p1].x - B * a[p1].y;
return abs(A * a[p2].x + B * a[p2].y + C) / dist(a[p1], a[p11]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int n, r;
double x, y;
fin>>n;
fin>>x>>y;
point temp;
temp.x = x;
temp.y = y;
v[0] = temp;
for(int i=1; i <=n-1;i++)
{
fin>>x>>y;
point p;
p.x = x;
p.y = y;
v[i] = p;
if( ((y - v[0].y) <= -eps) || ( (fabs(y - v[0].y) < eps) && ( (x - v[0].x) <= eps)))
swap(v[0], v[i]);
}
low = v[0];
sort(v + 1, v + n, cmp);
v[n] = low;
h[1] = 0;
h[2] = 1;
int top = 2;
int i =2;
while(i <=n)
{
if(ccw(v[h[top-1]], v[h[top]], v[i]) > 0){
h[++top] = i;
i++;
}
else top --;
}
for(int i = 1;i<= top -1; i++)
hull.push_back(v[h[i]]);
fout<<hull.size()<<"\n";
fout << fixed;
fout << setprecision(12);
for(int i =0; i < hull.size(); i++)
fout<<hull[i].x<< " "<<hull[i].y<<"\n";
// n = hull.size();
// int p1 = 0;
// int p2 = 1;
// double ans = 1e18;
// double cur = -1.0;
// do {
// while (true) {
// double nw = normal(hull, p1, p2);
// // cout << nw << ' ' << p1 << ' ' << p2 << '\n';1
// if (nw >= cur) {
// cur = nw;
// p2++;
// p2 = (p2 + n) % n;
// if (p2 == p1) {
// break;
// }
// } else {
// p2--;
// p2 = (p2 + n) % n;
// break;
// }
// }
// ans = min(ans, cur);
// cur = -1.0;
// p1++;
// } while(p1 != n);
//
// cout << fixed;
// cout << setprecision(12);
// cout << ans << "\n";
return 0;
}