Submission #859487

#TimeUsernameProblemLanguageResultExecution timeMemory
859487mychecksedadSIR (COI15_sir)C++17
0 / 100
361 ms23844 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 1e6+100, M = 1e5+10, K = 22; struct P{ ll x, y; void read(){ cin >> x >> y; } ll operator * (const P &other) const{ return x * other.y - y * other.x; } P operator - (const P &other) const{ return P{x - other.x, y - other.y}; } bool operator < (const P &other) const{ return (x == other.x ? y < other.y : x < other.x); }; }; int point_loc(P a, P b, P c){ // where is point c according to (a,b) b = b - a; c = c - a; if(b * c > 0) return 2; // upper if(b * c < 0) return 0; // under return 1; // on } struct Polygon{ vector<P> poly; Polygon(int n){ poly.resize(n); for(auto &p: poly) p.read(); } void ConvexHull(){ sort(all(poly)); vector<P> ch; for(int i = 0; i < poly.size(); ++i){ while(ch.size() > 1 && point_loc(ch[ch.size() - 2], ch[ch.size() - 1], poly[i]) >= 1){ ch.pop_back(); } ch.pb(poly[i]); } reverse(all(poly)); // for(auto p: ch){ // cout << p.x << ' ' << p.y << '\n'; // } // en; ch.pop_back(); for(int i = 0; i < poly.size(); ++i){ while(ch.size() > 1 && point_loc(ch[ch.size() - 2], ch[ch.size() - 1], poly[i]) >= 1){ ch.pop_back(); } ch.pb(poly[i]); } ch.pop_back(); poly = ch; } }; int n, m; void solve(){ cin >> n; Polygon cheese(n); cin >> m; Polygon pepper(m); cheese.ConvexHull(); pepper.ConvexHull(); ll ans = 0; vector<int> tang(cheese.poly.size()); m = pepper.poly.size(); n = cheese.poly.size(); // en; // for(auto p: cheese.poly){ // cout <<p.x << ' ' << p.y << '\n'; // } // en; // for(auto p: pepper.poly){ // cout <<p.x << ' ' << p.y << '\n'; // } // en; if(m > 1){ tang[0] = m - 1; for(int i = 0; i < m - 1; ++i){ if(point_loc(cheese.poly[0], pepper.poly[i], pepper.poly[i + 1]) == 0){ tang[0] = i; break; } } // cout << "g " << endl; for(int i = 1; i < cheese.poly.size(); ++i){ tang[i] = tang[i - 1]; while(point_loc(cheese.poly[i], pepper.poly[tang[i] % m], pepper.poly[(tang[i] + 1) % m]) != 0){ tang[i]++; tang[i] %= m; } cout << tang[i] << endl; } }else{ for(int i = 0; i < n; ++i) tang[i] = 0; } ll cur = 0; int cp = 1; for(int i = 0; i < cheese.poly.size(); ++i){ while(point_loc(cheese.poly[i], pepper.poly[tang[i]], cheese.poly[(cp + 1) % n]) == 2){ ++cp; cur += abs((cheese.poly[cp % n] - cheese.poly[i]) * (cheese.poly[(i + 1) % n] - cheese.poly[i])); } ans = max(ans, cur); cur -= abs((cheese.poly[(i + 1) % n] - cheese.poly[i]) * (cheese.poly[cp % n] - cheese.poly[(i + 1) % n])); // cout << cur << ' ' << cp << endl; } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

sir.cpp: In member function 'void Polygon::ConvexHull()':
sir.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < poly.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
sir.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < poly.size(); ++i){
      |                    ~~^~~~~~~~~~~~~
sir.cpp: In function 'void solve()':
sir.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1; i < cheese.poly.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
sir.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<P>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i = 0; i < cheese.poly.size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
sir.cpp: In function 'int main()':
sir.cpp:130:15: warning: unused variable 'aa' [-Wunused-variable]
  130 |   int tt = 1, aa;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...