fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const int N = 500;
  8. struct cord{
  9.     ll x,y;
  10. };
  11. ll dis(cord a, cord b){
  12.     return abs(a.x - b.x) + abs(a.y - b.y); 
  13. }
  14. ll calc(cord a, cord b, cord c){
  15.     ll dx1 = a.x - b.x;
  16.     ll dy1 = a.y - b.y;
  17.     ll dx2 = c.x - b.x;
  18.     ll dy2 = c.y - b.y;
  19.  
  20.     ll cross = dx1 * dy2 - dy1 * dx2;
  21.  
  22.     if (cross == 0) return 2; // straight
  23.     if (cross > 0) return 1;  // one turn direction
  24.     return 3;                 // the other turn direction
  25. }
  26. const ll Mod = 1000000009LL;
  27. const ll Base = 271LL;
  28.  
  29. struct hashed_string{
  30.     private:
  31.     string s; ll n;
  32.     vector <ll> prefix;
  33.     vector <ll> pow;
  34.     public:
  35.     hashed_string(){
  36.         n = 0;
  37.         prefix.assign(N, 0);
  38.         ll sum = 0;
  39.         pow.assign(N+1, 0);
  40.         pow[0] = 1;
  41.         for (int i = 1; i <= N; i++){
  42.             pow[i] = (pow[i-1] * Base) % Mod;
  43.         }
  44.     }
  45.     void add_hash(ll a){
  46.         prefix[n] = a % mod; if (n >= 1) prefix[n] = (prefix[n] + prefix[n-1] * Base) % Mod;
  47.         n++;    
  48.     }
  49.     ll get_full(){
  50.         return prefix[n-1];
  51.     }
  52.     ll get_hash(ll l, ll r){
  53.         ll x = prefix[r];
  54.         if (l >= 1){
  55.             l--;
  56.             x = ((x - prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;
  57.         }
  58.         return x;
  59.     }
  60. };
  61. void solve() {
  62.     ll n;
  63.     cin >> n;
  64.     deque <cord> l1(n);
  65.     for (int i = 0; i < n; i++) cin >> l1[i].x >> l1[i].y;
  66.     vector <ll> angle(n);
  67.     for (int i= 0; i < n; i++){
  68.         angle[i] = calc(l1[(i - 1 + n) % n], l1[i], l1[(i + 1) % n]);
  69.     }
  70.     auto find_dis = [&](ll i) -> ll{
  71.         if (i == 0) return 0LL;
  72.         ll x1 = 0; ll org = i;
  73.         while (i != 0){
  74.             x1 += dis(l1[i], l1[(i + 1) % n]);
  75.             i = (i + 1) % n;
  76.         }
  77.         i = org;
  78.         ll x2 = 0;
  79.         while (i > 0){
  80.             x2 += dis(l1[i], l1[i - 1]);
  81.             i--;
  82.         }
  83.         return min(x1, x2);
  84.     };
  85.     map <ll,ll> f;
  86.     for (int i = 1; i < n; i++){
  87.         hashed_string v = hashed_string();
  88.         v.add_hash(angle[i]);
  89.         f[v.get_full()] += 1;
  90.         for (int j = i + 1; j < n; j++){
  91.             v.add_hash(dis(l1[j], l1[j - 1]));
  92.             v.add_hash(angle[j]);
  93.             f[v.get_full()] += 1;
  94.         }
  95.     }   
  96.     vector <ll> g(n);
  97.     g[0] = 0;
  98.     for (int i = 1; i < n; i++){
  99.         hashed_string v = hashed_string();
  100.         v.add_hash(angle[i]);
  101.         if (f[v.get_full()] <= 1){
  102.             g[i] = find_dis(i);
  103.             continue;
  104.         }
  105.         ll cur = 0; bool flag = false;
  106.         for (int j = i + 1; j < n; j++){
  107.             cur += dis(l1[j], l1[j-1]);
  108.             v.add_hash(dis(l1[j], l1[j - 1]));
  109.             v.add_hash(angle[j]);
  110.             if (f[v.get_full()] <= 1){
  111.                 g[i] = find_dis(j) + cur;
  112.                 flag = true;
  113.                 break;
  114.             }
  115.         }
  116.         if (!flag){
  117.             g[i] = dis(l1[n-1], l1[0]) + cur;
  118.         }
  119.     }   
  120.     ll answ = 0;
  121.     for (int i = 0; i < n; i ++){
  122.         answ = max(answ, g[i] - find_dis(i));
  123.     }
  124.     cout << answ << "\n";
  125. }
  126.  
  127. int main() {
  128.     freopen("lightsout.in","r",stdin);
  129.     freopen("lightsout.out","w",stdout);
  130.     ios::sync_with_stdio(false);
  131.     cin.tie(nullptr);
  132.  
  133.     ll t = 1;
  134.     while (t--) {
  135.         solve();
  136.     }
  137.  
  138.     return 0;
  139. }
Runtime error #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sVvRkd
language:
C++14 (clang 8.0)
created:
4 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!