Submission #152607

#	Time	Username	Problem	Language	Result	Execution time	Memory
152607		Mercenary	Triangles (CEOI18_tri)	C++14	20 / 100	10 ms	380 KiB

tri

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

//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);
//}

const int maxn = 4e4 + 5;
int n , id[maxn];
int a[maxn];
int main(){
    srand(time(0));
//    init();
    n = get_n();
    int u = rand() % n + 1;
    for(int i = 1 ; i <= n ; ++i){
        id[i] = i;
    }
    swap(id[u] , id[1]);
    sort(id + 2 , id + n + 1 , [&](const int & x , const int &y){
            return !is_clockwise(u , x , y);
         });
    int m = 0;
    for(int i = 1 ; i <= n ; ++i){
        while(m >= 2 && is_clockwise(a[m - 1] , a[m] , id[i]))--m;
        a[++m] = id[i];
    }
//    give_answer(m);
    int pre = m;
    u = a[rand() % m + 1];
    for(int i = 1 ; i <= n ; ++i){
        id[i] = i;
    }
    swap(id[u] , id[1]);
    sort(id + 2 , id + n + 1 , [&](const int & x , const int &y){
            return !is_clockwise(u , x , y);
         });
    m = 0;
    for(int i = 1 ; i <= n ; ++i){
        while(m >= 2 && is_clockwise(a[m - 1] , a[m] , id[i]))--m;
        a[++m] = id[i];
    }
    while(m != pre){
        pre = m;
        u = a[rand() % m + 1];
        for(int i = 1 ; i <= n ; ++i){
            id[i] = i;
        }
        swap(id[u] , id[1]);
        sort(id + 2 , id + n + 1 , [&](const int & x , const int &y){
                return !is_clockwise(u , x , y);
             });
        m = 0;
        for(int i = 1 ; i <= n ; ++i){
            while(m >= 2 && is_clockwise(a[m - 1] , a[m] , id[i]))--m;
            a[++m] = id[i];
        }
    }
    give_answer(m);
}

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