Submission #74272

#TimeUsernameProblemLanguageResultExecution timeMemory
74272dsabolicSIR (COI15_sir)C++17
0 / 100
34 ms1220 KiB
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 1e5 + 50; pii pivot; int n, m; pii points[N]; pii peppers[N]; vector<pii> hull; ll gccw(pii a, pii b, pii c) { return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y); } int ccw(pii a, pii b, pii c) { int get = gccw(a, b, c); if(get > 0) return -1; else if(!get) return 0; return 1; } ll pow(ll a) { return a * a; } ll dist(pii a, pii b) { return pow((ll)a.Y - b.Y) + pow((ll)a.X - b.X); } bool cmpconvex(pii a, pii b) { int get = ccw(pivot, a, b); if(!get) return dist(pivot, a) < dist(pivot, b); return get == -1; } void cons_convex() { int idx = 0; for(int i = 1; i < m; ++i) if(peppers[idx] > peppers[i]) idx = i; swap(peppers[0], peppers[idx]); sort(peppers + 1, peppers + m, cmpconvex); if(m == 1) { hull.push_back(peppers[0]); return; } hull.push_back(peppers[0]); hull.push_back(peppers[1]); for(int i = 2; i < m; ++i) { pii top = hull.back(); hull.pop_back(); while(!hull.empty() && ccw(pivot, top, peppers[i]) != -1) top = hull.back(), hull.pop_back(); hull.push_back(top); hull.push_back(peppers[i]); } } int next(int i) { return (i + 1) % hull.size(); } int nextj(int i) { return (i + 1) % n; } int area(pii a, pii b, pii c) { return abs(gccw(a, b, c)); } void load_solve() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d", &points[i].X, &points[i].Y); scanf("%d", &m); for(int i = 0; i < m; ++i) scanf("%d%d", &peppers[i].X, &peppers[i].Y); cons_convex(); int j = 1, k = 0; ll maxarea = 0, curr_area = 0; for(int i = 0; i < n; ++i) { // fiskiramo pocetak reza while(ccw(points[i], hull[k], hull[next(k)]) == 1LL) k = next(k); while(ccw(points[i], hull[k], points[nextj(j)]) == 1LL) curr_area += area(points[i], points[j], points[nextj(j)]), j = nextj(j); // printf("I: %d, J: %d, K: %d, AREA: %lld\n", i, j, k, curr_area); maxarea = max(maxarea, curr_area); if(i < n - 1) curr_area -= area(points[i], points[i + 1], points[j]); } printf("%lld\n", maxarea); } int main() { load_solve(); return 0; }

Compilation message (stderr)

sir.cpp: In function 'void load_solve()':
sir.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sir.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &points[i].X, &points[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sir.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &peppers[i].X, &peppers[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...