Submission #1152646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152646		simuyu	Geometrija (COCI21_geometrija)	C++20	0 / 110	0 ms	320 KiB

geometrija

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second

ll N;
ll xs[1005];
ll ys[1005];
ll minx, maxx, miny, maxy, maxyx;
ll minxidx, maxxidx, minyidx, maxyidx;
ll num_pts;
ll cx, cy, cidx;
ll dx, dy, bdx, bdy, bidx;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (ll i=0; i<N; i++) {
        cin >> xs[i] >> ys[i];
    }


    // extract mins and maxes
    minx = xs[0];
    minxidx = 0;
    maxx = xs[0];
    maxxidx = 0;
    for (ll i=1; i<N; i++) {
        if (xs[i] < minx) {
            minx = xs[i];
            minxidx = i;
        }
        if (xs[i] > maxx) {
            maxx = xs[i];
            maxxidx = i;
        }
    }

    miny = ys[0];
    minyidx = 0;
    maxy = ys[0];
    maxyidx = 0;
    maxyx = LLONG_MAX;
    for (ll i=1; i<N; i++) {
        if (ys[i] < miny) {
            miny = ys[i];
            minyidx = i;
        }
        if (ys[i] > maxy) {
            maxy = ys[i];
            maxyidx = i;
            maxyx = xs[i];
        } else if (ys[i] == maxy) { // modified so that i'll have the leftmost maxy (maxy with least x)
            if (xs[i] < maxyx) {
                maxyx = xs[i];
                maxyidx = i;
            }
        }
    }



    // start making convex hull from left topmost point (left max y)
    num_pts = 1;
    cx = xs[maxyidx];
    cy = ys[maxyidx];
    cidx = maxyidx;

    while (cx != maxx) { // while it isn't the rightmost point yet
        // find the next point
        bdy = 1;
        bdx = 0;
        bidx = cidx;
        for (ll i=0; i<N; i++) {
            if (i==cidx) continue;
            if (xs[i] <= cx) continue; // if dx==0 then it can't be good
            if (ys[i] > cy) {
                // CONTRADICTION!!
                cout << "CONTRADICTION: the y increased while x decreased!! (at first hull finder)" << endl;
                1/0;
            }
            dy = cy - ys[i]; // absolute value. as cy>=ys[i] for sure.
            dx = xs[i] - cx; // as it has to be to the right rn


            if ( (bdx == 0) || (((double)dy)/dx < ((double)bdy)/bdx) ) {
                // abs(dy/dx) is less than the best so far!
                bdy = dy;
                bdx = dx;
                bidx = i;
            }
        }

        if (bidx == cidx) {
            // CANNOT BE!
            cout << "CONTRADICTION: BIDX==CIDX!! (at first hull finder)" << endl;
            1/0;
        }

        // next point should be bidx.
        //cout << "1 ADDING POINT " << bidx << " (" << xs[bidx] << "," << ys[bidx] << ")" << endl;
        num_pts++;
        cx = xs[bidx];
        cy = ys[bidx];
        cidx = bidx;
    }

    // now it's already got to the rightmost point. It's at the top rightmost point.
    // let's continue with these rotation-inspired calculations
    // repeat till we're at miny
    while ( cy != miny ) {
        bdx = 1;
        bdy = 0;
        bidx = cidx;
        for (ll i=0; i<N; i++) {
            if (i==cidx) continue;
            if (ys[i] >= cy) continue; // if dy==0 then it can't be good
            if (xs[i] > cx) {
                cout << "CONTRADICTION: the x increased while the y decreased! (at second hull finder)" << endl;
                1/0;
            }
            // compare the dx/dy
            dx = cx - xs[i];
            dy = cy - ys[i];
            if ((bdy == 0) || ( ((double)dx)/dy < ((double)bdx)/bdy ) ) {
                // found better one
                bdy = dy;
                bdx = dx;
                bidx = i;
            }
        }

        if (bidx == cidx) {
            cout << "CONTRADICTION: BIDX==CIDX!! (at second hull finder)" << endl;
        }


        // next point should be bidx.
        //cout << "2 ADDING POINT " << bidx << " (" << xs[bidx] << "," << ys[bidx] << ")" << endl;
        num_pts++;
        cx = xs[bidx];
        cy = ys[bidx];
        cidx = bidx;
    }




    // now it's at the right bottommost point

    while (cx != minx) { // while it isn't the leftmost point yet
        // find the next point
        bdy = 1;
        bdx = 0;
        bidx = cidx;
        for (ll i=0; i<N; i++) {
            if (i==cidx) continue;
            if (xs[i] >= cx) continue; // if dx==0 then it can't be good
            if (ys[i] < cy) {
                // CONTRADICTION!!
                cout << "CONTRADICTION: the y decreased while x increased!! (at third hull finder)" << endl;
                1/0;
            }
            dy = ys[i] - cy; // absolute value. as cy>=ys[i] for sure.
            dx = cx - xs[i]; // as it has to be to the right rn


            if ( (bdx == 0) || (((double)dy)/dx < ((double)bdy)/bdx) ) {
                // abs(dy/dx) is less than the best so far!
                bdy = dy;
                bdx = dx;
                bidx = i;
            }
        }

        if (bidx == cidx) {
            // CANNOT BE!
            cout << "CONTRADICTION: BIDX==CIDX!! (at third hull finder)" << endl;
            1/0;
        }

        // next point should be bidx.
        //cout << "3 ADDING POINT " << bidx << " (" << xs[bidx] << "," << ys[bidx] << ")" << endl;
        num_pts++;
        cx = xs[bidx];
        cy = ys[bidx];
        cidx = bidx;
    }


    // now it's at the bottom leftmost point
    // let's continue with these rotation-inspired calculations
    // repeat till we're at maxy (the point we started with)
    while ( cy != maxy ) {
        bdx = 1;
        bdy = 0;
        bidx = cidx;
        for (ll i=0; i<N; i++) {
            if (i==cidx) continue;
            if (ys[i] <= cy) continue; // if dy==0 then it can't be good
            if (xs[i] < cx) {
                cout << "CONTRADICTION: the x decreased while the y increased! (at fourth hull finder)" << endl;
                1/0;
            }
            // compare the dx/dy
            dx = xs[i] - cx;
            dy = ys[i] - cy;
            if ((bdy == 0) || ( ((double)dx)/dy < ((double)bdx)/bdy ) ) {
                // found better one
                bdy = dy;
                bdx = dx;
                bidx = i;
            }
        }

        if (bidx == cidx) {
            cout << "CONTRADICTION: BIDX==CIDX!! (at fourth hull finder)" << endl;
        }


        // next point should be bidx.
        //cout << "4 ADDING POINT " << bidx << " (" << xs[bidx] << "," << ys[bidx] << ")" << endl;
        num_pts++;
        cx = xs[bidx];
        cy = ys[bidx];
        cidx = bidx;
    }

    num_pts --;


    //cout << "NUM PTS: " << num_pts << endl;


    // corner case: only 1 point inside
    if (num_pts+1 == N) {
        cout << 2*num_pts << endl;
    } else {
        cout << num_pts << endl;
    }


    return 0;
}

Compilation message (stderr)

geometrija.cpp: In function 'int main()':
geometrija.cpp:84:18: warning: division by zero [-Wdiv-by-zero]
   84 |                 1/0;
      |                 ~^~
geometrija.cpp:101:14: warning: division by zero [-Wdiv-by-zero]
  101 |             1/0;
      |             ~^~
geometrija.cpp:124:18: warning: division by zero [-Wdiv-by-zero]
  124 |                 1/0;
      |                 ~^~
geometrija.cpp:166:18: warning: division by zero [-Wdiv-by-zero]
  166 |                 1/0;
      |                 ~^~
geometrija.cpp:183:14: warning: division by zero [-Wdiv-by-zero]
  183 |             1/0;
      |             ~^~
geometrija.cpp:207:18: warning: division by zero [-Wdiv-by-zero]
  207 |                 1/0;
      |                 ~^~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60