Cod sursa(job #2730771)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 26 martie 2021 20:34:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.96 kb
#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;
}