Submission #72616

#	Time	Username	Problem	Language	Result	Execution time	Memory
72616		istlemin	Triangles (CEOI18_tri)	C++14	100 / 100	48 ms	3348 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll ask(ll a,ll b,ll c){
    return is_clockwise(a+1,b+1,c+1);
}

ll n;

ll P;

bool comp(ll a,ll b){
    bool ans = ask(P,a,b);
    return ans;
}

vi getHullGivenPoint(ll p, vi points){
    auto it = find(all(points),p);
    if(it!=points.end()) points.erase(it);

    P = p;
    sort(all(points),comp);

    if(points.size()==0) return vi(1,p);

    /*rep(i,0,points.size()){
		cout<<points[i]<<" ";
    }
    cout<<endl;*/

    vi hull;
    hull.push_back(p);
    hull.push_back(points[0]);
    rep(i,1,points.size()){
		assert(hull.size()>=2);
        while(!ask(hull[hull.size()-2],hull[hull.size()-1],points[i])){
			hull.pop_back();
			assert(hull.size()>=2);
		}
		hull.push_back(points[i]);
    }
    return hull;
}

vi combineHulls(vi hull1,vi hull2){
    ll a1,a2,b1,b2;

    rep(w,0,2){
		ll i1 = 0;
		ll i2 = 0;

		ll a = hull1.size();
		ll b = hull2.size();

		while(true){
			if(!ask(hull1[i1],hull2[i2],hull2[(i2+1)%b])){
				i2 = (i2+1)%b;
			} else if(!ask(hull1[(i1+a-1)%a],hull1[i1],hull2[i2])){
				i1 = (i1+a-1)%a;
			} else break;
		}

        if(w==0) {
			a1 = i1;
			b1 = i2;
			if(a1==0) a1 = a;
		} else {
            a2 = i2;
            b2 = i1;
			if(b2==0) b2 = a;
		}

		swap(hull1,hull2);
	}
	ll a = hull1.size();
	ll b = hull2.size();


	vi res;
    rep(i,0,a+1){
        if(i>=a2&&i<=a1) res.push_back(hull1[i%a]);
    }
    rep(i,0,b+1){
        if(i>=b1&&i<=b2) res.push_back(hull2[i%b]);
    }

    return res;
}

bool isInHull(ll p){
    bool ans = false;
    rep(i,0,n){
		if(i==p) continue;
        bool left = false;
        bool right = false;
        rep(j,0,n){
			if(i==p||j==p||j==i) continue;
            if(ask(p,i,j)) left = true;
            else right = true;
        }
        if(!(left&&right))
			return true;
    }
    return ans;
}

int main(int argc,char** argv){
	cin.sync_with_stdio(false);

	n = get_n();
    vi points(n);
    rep(i,0,n) points[i] = i;

    /*string seed = argv[1];
    cout<<seed<<endl;
    srand(stoi(seed));*/

	srand(16);
    random_shuffle(all(points));

    ll a = points[0];
    ll b = points[1];
    //cout<<a<<" "<<b<<endl;

    vi points1;
    vi points2;

    rep(i,2,points.size()){
        if(ask(a,b,points[i])){
			points1.push_back(points[i]);
        } else {
			points2.push_back(points[i]);
        }
    }
    /*cout<<"Points 1: "<<endl;
    rep(i,0,points1.size()) cout<<points1[i]<<" ";
    cout<<endl;
    cout<<"Points 2: "<<endl;
    rep(i,0,points2.size()) cout<<points2[i]<<" ";
    cout<<endl;*/

	vi hull1 = getHullGivenPoint(a,points1);
	vi hull2 = getHullGivenPoint(b,points2);
    /*cout<<"Hull 1: "<<endl;
    rep(i,0,hull1.size()) cout<<hull1[i]<<" ";
    cout<<endl;
    cout<<"Hull 2: "<<endl;
    rep(i,0,hull2.size()) cout<<hull2[i]<<" ";
    cout<<endl;*/

    vi hull;
	if(hull1.size()==1) hull = getHullGivenPoint(hull1[0],points);
	else if(hull2.size()==1) hull = getHullGivenPoint(hull2[0],points);
	else hull = combineHulls(hull1,hull2);

    /*cout<<"Hull: "<<endl;
    rep(i,0,hull.size()) cout<<hull[i]<<" ";
    cout<<endl;*/


    /*ll realAns = 0;
    rep(i,0,n){
		realAns += isInHull(i);
    }
    assert(hull.size()==realAns);*/
    give_answer(hull.size());
}

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