Submission #950514

#	Time	Username	Problem	Language	Result	Execution time	Memory
950514		berr	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	600 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(v, 2, i)){
                v=i;
            }
        }
    }
    if(v==-1){
        for(int i=3; i<=n; i++){
            if(is_clockwise(2, 1, i)){
                if(v==-1) v=i;
                else if(is_clockwise(v, 1, i)){
                    v=i;
                }
            }
        }
    
        int u=-1;
   
        for(int i=2; i<=n; i++){
            if(i==v||i==1) continue;
            if(is_clockwise(1, v, i)){
                if(u==-1) u=i;
                else if(is_clockwise(u, v, i)){
                    u=i;
                }
            }
        }

        assert(u!=-1);
        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(flag, u, i)){
                        flag = i;
                    }
                }
            }
            if(vis[flag]||flag==0) break;
            
            vis[flag] = 1;
            u=flag;
            
        }

        int ans=0;
        for(auto i: vis) ans+=i;

        give_answer(ans);

    }
    else{

        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(u, v, i)){
                    u=i;
                }
            }
        }
        assert(u!=-1);
        vector<int> vis(n+1);
        vis[u]=1;
        vis[v]=1;
        int flag=1, h=500;
        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(flag, u, i)){
                        flag = i;
                    }
                }
            }
            if(vis[flag]||flag==0) break;
            vis[flag] = 1;
             u=flag;
            
        }

        int ans=0;
        for(auto i: vis) ans+=i;

        give_answer(ans);
        
    }
}   

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:131:21: warning: unused variable 'h' [-Wunused-variable]
  131 |         int flag=1, h=500;
      |                     ^

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