제출 #231372

#제출 시각아이디문제언어결과실행 시간메모리
231372farmerboyTriangles (CEOI18_tri)C++14
0 / 100
5 ms384 KiB
/* Author: Nguyen Tan Bao Status: Idea: */ #include <bits/stdc++.h> #define FI first #define SE second #define EPS 1e-9 #define ALL(a) a.begin(),a.end() #define SZ(a) int((a).size()) #define MS(s, n) memset(s, n, sizeof(s)) #define FOR(i,a,b) for (int i = (a); i <= (b); i++) #define FORE(i,a,b) for (int i = (a); i >= (b); i--) #define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) //__builtin_ffs(x) return 1 + index of least significant 1-bit of x //__builtin_clz(x) return number of leading zeros of x //__builtin_ctz(x) return number of trailing zeros of x using namespace std; using ll = long long; using ld = double; typedef pair<int, int> II; typedef pair<II, int> III; typedef complex<ld> cd; typedef vector<cd> vcd; const ll MODBASE = 1000000007LL; const int MAXN = 110; const int MAXM = 1000; const int MAXK = 16; const int MAXQ = 200010; int n; int get_n() { return 0; } void give_answer(int x) { } bool is_clockwise(int a, int b, int c) { return true; } vector<int> lef, rig, cmb, convexHull; bool cmp(int a, int b) { return is_clockwise(n,a,b); } int main() { ios::sync_with_stdio(0); cin.tie(nullptr); n = get_n(); FOR(i,2,n-1) if (is_clockwise(n,i,1)) lef.push_back(i); else rig.push_back(i); sort(ALL(lef), cmp); sort(ALL(rig), cmp); cmb.push_back(n); for (int x : lef) cmb.push_back(x); cmb.push_back(1); for (int x : rig) cmb.push_back(x); convexHull.push_back(cmb[0]); convexHull.push_back(cmb[1]); FOR(i,2,SZ(cmb)-1) { if (SZ(convexHull) >= 2 && !is_clockwise(convexHull[SZ(convexHull)-2], convexHull[SZ(convexHull)-1], cmb[i])) convexHull.pop_back(); convexHull.push_back(cmb[i]); } int la = SZ(convexHull)-1; int fi = 0; while (la - fi + 1 >= 3) { if (!is_clockwise(convexHull[la], convexHull[fi], convexHull[fi+1])) fi++; else if (!is_clockwise(convexHull[la-1], convexHull[la], convexHull[fi])) la--; else break; } give_answer(max(3, la-fi+1)); return 0; }
#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...