Submission #950488

#	Time	Username	Problem	Language	Result	Execution time	Memory
950488		berr	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	604 KiB

tri

#include <bits/stdc++.h>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "trilib.h"
/*
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);
}*/
 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n=get_n();
 
    int v=-1;
 
    for(int i=3; i<=n; i++){
        if(is_clockwise(1, 2, i)){
            if(v==-1) v=i;
            else if(is_clockwise(2, i, v)){
                v=i;
            }
        }
    }
    // v is on the borders
    int u=-1;
   
    for(int i=1; i<=n; i++){
        if(i==v||i==2) continue;
        if(is_clockwise(2, v, i)){
            if(u==-1) u=i;
            else if(is_clockwise(v, i, u)){
                u=i;
            }
        }
    }
 
 
    vector<int> vis(n+1);
    vis[u]=1;
    vis[v]=1;
    int flag=1;
    while(flag){
        flag=0;
        for(int i=1; i<=n; i++){
            if(i==u || i==v) continue;
            if(is_clockwise(v, u, i)){
                if(flag==0) flag=i;
                else if(is_clockwise(u, i, flag)){
                    flag = i;
                }
            }
        }
        if(vis[flag]||flag==0) break;
        
        vis[flag] = 1;
        v=u; u=flag;
        
    }
 
    int ans=0;
    for(auto i: vis) ans+=i;
 
    give_answer(ans);
}

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