Submission #122461

#	Time	Username	Problem	Language	Result	Execution time	Memory
122461		rajarshi_basu	Triangles (CEOI18_tri)	C++14	75 / 100	3034 ms	2296 KiB

tri

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <unordered_map>
#include <chrono>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector

#include "trilib.h"

using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
/*
ii pnts[6] = {{1,1},{4,3},{2,2},{1,4},{5,1},{3,2}} ;
int get_n(){
    //pnts = {}
    return 6;
}

int cross(ii a,ii b,ii c){
    int x1 = a.ff-c.ff;
    int x2 = b.ff-c.ff;
    int y1 = a.ss-c.ss;
    int y2 = b.ss-c.ss;
    return x1*y2-x2*y1;
}

bool is_clockwise(int a,int b,int c){
    a--;b--;c--;
    return cross(pnts[a],pnts[b],pnts[c]) < 0;
}
*/


int getRand(int n){
    return rng() % n;
}


int n;
int* arr;
int countCl(int a,int b){
    random_shuffle(arr,arr+n,getRand);
    FOR(i,n){
        if(arr[i] == a or arr[i] == b)continue;
        if(is_clockwise(a,b,arr[i]))return arr[i];
    }
    return -1;
}

int findCorner(){
    int a = 1;
    int b = 2;
    int cnt = 0;

    while(1){
        cnt++;
        int nd = countCl(a,b);
        if(nd == -1)break;
        if(cnt%2 == 0){
            a = nd;
        }else{
            b = nd;
        }
    }
    return a;
}

int hull(int c){
    //return 0;
    int p[n];
    FOR(i,n){
        p[i] = i+1;
    }
    swap(p[0],p[c-1]);
    //return 0;
    sort(p+1,p+n,[&](int a,int b){
        return !is_clockwise(c,a,b);
    }); 
    deque<int> st;
    int ptr = 0;
    //return 0;
    //cout << "got here" << endl;
    while(1){
        while(st.size() > 1 and is_clockwise(st[(int)st.size()-2],st[(int)st.size()-1],p[ptr]))st.pop_back();
        st.push_back(p[ptr]);
        ptr++;
        if(ptr == n)break;
    }

    while(st.size() > 1 and is_clockwise(st[(int)st.size()-2],st[(int)st.size()-1],p[0]))st.pop_back();
    return st.size();      
}

int main(){
    n = get_n();
    arr = new int[n];
    FOR(i,n)arr[i] = i+1;
    give_answer(hull(findCorner()));
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25