Submission #585059

#	Time	Username	Problem	Language	Result	Execution time	Memory
585059		hibiki	Triangles (CEOI18_tri)	C++11	20 / 100	3076 ms	304 KiB

tri

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

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

static int N;
static long long *x, *y;
static int queries=0;

static void init() {
	static int is_inited=0;
	if (is_inited)
		return;
	is_inited=1;
	assert(scanf("%d", &N)==1);
	x=(long long*)malloc((N+1)*sizeof(long long));
	y=(long long*)malloc((N+1)*sizeof(long long));
	for (int i=1; i<=N; i++)
		assert(scanf("%lld%lld", &x[i], &y[i])==2);
}

int get_n() {
	init();
	return N;
}

int is_clockwise(int a, int b, int c) {
	init();
	assert(a>=1 && a<=N);
	assert(b>=1 && b<=N);
	assert(c>=1 && c<=N);
	assert(a!=b && a!=c && b!=c);
	queries++;
        if(queries == 1000 * 1000 + 1)
            printf("Too many queries!");
	return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0;
}

void give_answer(int s) {
	init();
	printf("%d\n", s);
}

int n, cnt = 0, st;
vector<int> v, stk1, stk2;



int main()
{
    n = get_n();
    v.pb(1);
    v.pb(2);
    for(int i = 3; i <= n; i++)
    {
        while(sz(v) > 1 && is_clockwise(v[sz(v) - 2], v[sz(v) - 1], i))
            v.pop_back();
        v.pb(i);
    }
    cnt = 1;
    st = v[1];
    int lst = v[1];
    while(1)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i == lst) continue;
            bool ok = true;
            for(int j = 1; j <= n; j++)
            {
                if(j == i || j == lst) continue;
                if(!is_clockwise(lst, i, j))
                {
                    ok = false;
                    break;
                }
            }
            if(ok)
            {
                // printf("%d %d\n",lst,i);
                if(i == st)
                {
                    give_answer(cnt);
                    return 0;
                }
                cnt++;
                lst = i;
                break;
            }
        }
    }
    return 0;
}

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