Submission #405445

#TimeUsernameProblemLanguageResultExecution timeMemory
405445ollelTriangles (CEOI18_tri)C++14
55 / 100
2260 ms262148 KiB
#include <bits/stdc++.h>
#include <iostream>
#include "trilib.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tuple<int,int,int> tiii;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

int n, guesses = 1e6;

map<tiii, bool> cw;

bool clockwise(int a, int b, int c){
  tiii t = make_tuple(a, b, c);
  if (cw.find(t) != cw.end()) return cw[t];
  bool ans = is_clockwise(a, b, c);
  cw[{a, b, c}] = cw[{b, c, a}] = cw[{c, a, b}] = ans;
  cw[{a, c, b}] = cw[{c, b, a}] = cw[{b, a, c}] = !ans;
  return ans;
}

bool hull(int a, int b) {
  rep(c, 1, n + 1) {
    if (c == a || c == b) continue;
    if (!clockwise(a, b, c)) return false;
  }
  return true;
}

int find_neighbor(int a) {
  //a down, b up
  int b = (a != 1) ? 1:2;

  rep(c, 1, n+1) {
    if (c == a || c == b) continue;
    if (clockwise(a, c, b)) b = c;
  }

  return b;
}

int main()
{
  n = get_n();
  set<int> h;
  rep(i, 1, n + 1) {
    int j = find_neighbor(i);
    if (hull(i, j) || hull(j, i)) {h.insert(i); h.insert(j);}
  }
  cout << h.size() << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...