oj.uz

Submission #942542

# Submission time Handle Problem Language Result Execution time Memory
942542 2024-03-10T20:34:43 Z vjudge1 Index (COCI21_index) C++17
0 / 110
 2500 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

const ld eps = 1e-8;

#define int ll

#define sz(x) (int)x.size()

struct point {
    int x, y;
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<point> points(n);
    vector<int> x(n), y(n);
    for(int i=0; i<n; ++i){
        cin >> points[i].x >> points[i].y;
        x[i] = points[i].x;
        y[i] = points[i].y;
    }

    int ans = 0;

    for(int i=0; i<n; ++i){
        for(int j=i+1; j<n; ++j){

            // AB
            bool ok = 1;

            for(int k=0; k<n; ++k){
                if(k == j or k == i) continue;

                for(int l=k+1; l<n; ++l){
                    if(l == j or l == i) continue;

                    // CD

                    int xa = x[i];
                    int ya = y[i];
                    int xb = x[j];
                    int yb = y[j];

                    ld m1 = 1.0 * (ya - yb) / (xa - xb);

                    int xc = x[k];
                    int yc = y[k];
                    int xd = x[l];
                    int yd = y[l];

                    ld m2 = 1.0 * (yc - yd) / (xc - xd);

                    if(abs(m2 - m1) < eps){
                        continue;
                    }

                    ld x = 1.0 * (m1 * xa - m2 * xc + yc - ya) / (m1 - m2);
                    ld y = m1 * x - m1 * xa + ya;


                    bool tmp = min(xa, xb) <= x && x <= max(xa, xb) && min(ya, yb) <= y && y <= max(ya, yb) && min(xc, xd) <= x && x <= max(xc, xd) && min(yc, yd) <= y && y <= max(yc, yd);

                    if(abs(x - xa) < eps or abs(y - ya) < eps){
                        continue;
                    }

                    if(tmp){
                        // cerr << "el segmento: " << xa << ya << ' ' << xb << yb << endl;
                        // cerr << "choca con el segmento " << xc << yc << ' ' << xd << yd << endl;
                        // cerr << "en " << x << ' ' << y << endl;
                        ok = 0;
                    }

                }

            }

            ans += ok;

        }
    }

    cout << ans;

}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2548 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2548 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2548 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -