oj.uz

답안 #859543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859543 2023-10-10T10:00:02 Z mychecksedad SIR (COI15_sir) C++17
100 / 100
 136 ms 35532 KB 
/* 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 0; // upper
  if(b * c < 0) return 2; // 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]) == 0){
        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]) == 0){
        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){
    for(int i = 0; i < m; ++i){
      if(point_loc(cheese.poly[0], pepper.poly[i], pepper.poly[(i + 1) % m]) == 2){
        tang[0] = i;
        break;
      }
    }
    // cout << "g " << endl;
    for(int i = 1; i < n; ++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;
      }
    }
  }else{
    for(int i = 0; i < n; ++i) tang[i] = 0;
  }
  ll cur = 0;
  int cp = 1;
  for(int i = 0; i < n; ++i){
    while(point_loc(cheese.poly[i], pepper.poly[tang[i]], cheese.poly[(cp + 1) % n]) == 0){
      cur += abs((cheese.poly[cp % n] - cheese.poly[i]) * (cheese.poly[(cp + 1) % n] - cheese.poly[i]));
      ++cp;
    }

    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

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 'int main()':
sir.cpp:128:15: warning: unused variable 'aa' [-Wunused-variable]
  128 |   int tt = 1, aa;
      |               ^~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 860 KB Output is correct

Subtask #3
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 13000 KB Output is correct
2 Correct 136 ms 22996 KB Output is correct
3 Correct 111 ms 21756 KB Output is correct
4 Correct 38 ms 11720 KB Output is correct
5 Correct 99 ms 17592 KB Output is correct
6 Correct 131 ms 35532 KB Output is correct