oj.uz

답안 #567173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567173 2022-05-23T08:49:06 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 2641 ms 1996 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;

struct Vector {
  ll x;
  ll y;
};

ll f(Vector a, Vector b) {
  return (a.x - b.x) * (ll) (a.y + b.y);
}

ll f(Vector a, Vector b, Vector c) {
  return f(a, b) + f(b, c) + f(c, a);
}

Vector operator + (Vector a, Vector b) {
  return { a.x + b.x, a.y + b.y };
}

Vector operator - (Vector a, Vector b) {
  return { a.x - b.x, a.y - b.y };
}

Vector operator * (Vector a, ll b) {
  return { a.x * b, a.y * b };
}


Vector operator * (ll b, Vector a) {
  return { a.x * b, a.y * b };
}


Vector readVector() {
  int x, y;
  cin >> x >> y;
  return { x, y };
}

const int N = 2000 + 7;
const int C = 10000 + 7;

int w, h;
int n, c;
int cnt_good[C];
Vector camps[C];
Vector trees[N];
Vector myself;

const ld eps=1e-14;

bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return atan2((ld)a.first.y, (ld)a.first.x) - atan2((ld)b.first.y, (ld)b.first.x)<eps;
}

int get_type(Vector a) {

  if (a.x == w) return 0;
  if (a.y == h) return 1;
  if (a.x == 0) return 2;
  if (a.y == 0) return 3;
}

bool cmpOnRect(int i, int j) {
  Vector a = camps[i];
  Vector b = camps[j];

  int type_a = get_type(a);
  int type_b = get_type(b);
  if (type_a != type_b) return type_a < type_b;
  int type = type_a;

  if (type == 0) {
    return a.y < b.y;
  }
  if (type == 1) {
    return a.x > b.x;
  }
  if (type == 2) {
    return a.y > b.y;
  }
  if (type == 3) {
    return a.x < b.x;
  }
}

ld get_f(pair<ld, ld> a, pair<ld, ld> b) {
  return (a.first - b.first) * (a.second + b.second);
}

ld get_f(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
  return get_f(a, b) + get_f(b, c) + get_f(c, a);
}

int get_cadran(pair<ld, ld> a) {
  if (a.first >= 0) {
    if (a.second >= 0) {
      return 0;
    } else {
      return 3;
    }
  } else {
    if (a.second <= 0) {
      return 2;
    } else {
      return 1;
    }
  }
}

int tr_cadran(int c) {
  return (c + 2) % 4;
}

bool cmp_pld(pair<ld, ld> a, pair<ld, ld> b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(cadran_b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (get_f(pair<ld, ld> (0, 0), a, b) > 0);
}



int get_cadran(Vector a) {
  if (a.x >= 0) {
    if (a.y > 0) {
      return 0;
    } else {
      return 3;
    }
  } else {
    if (a.y < 0) {
      return 2;
    } else {
      return 1;
    }
  }
}

bool cmp_Vector(Vector a, Vector b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(cadran_b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (f({0, 0}, a, b) > 0);
}

bool cmp2(pair<Vector, int> a, pair<Vector, int> b) {
  return cmp_Vector(a.first, b.first);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

///  freopen ("input.txt", "r", stdin);


  cin >> w >> h;
  myself = readVector();

  vector<int> inds;

  cin >> c;
  for (int i = 1; i <= c; i++) {
    camps[i] = readVector();
    inds.push_back(i);
  }
  sort(inds.begin(), inds.end(), cmpOnRect);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    trees[i] = readVector();
  }



  for (int tid = 1; tid <= n; tid++) {
    Vector origin = trees[tid];
    vector<pair<Vector, int>> events;
    for (int i = 1; i <= n; i++) {
      if (i == tid) continue;
      Vector delta = trees[i] - origin;
      events.push_back({ {-delta.x,-delta.y}, -1 });
    }
    events.push_back({ myself - origin, 0 });


    auto cop_events = events;

    ld minAng = (ld)1e18;
    int start = -1;

    for (int P = 0; P < c; P++) {
      int i = inds[P];
      Vector vec = camps[i] - origin;
      ld ang = atan2(vec.y, vec.x);
      if (ang < minAng) {
        minAng = ang;
        start = P;
      }
    }

    vector<pair<Vector, int>> cps;
    for (int l = 0; l < c; l++) {
      int i = inds[(start + l) % c];
      cps.push_back({ camps[i] - origin, i });
    }



    sort(cop_events.begin(), cop_events.end(), cmp2);


    vector<pair<Vector, int>> so;

    int p1 = 0, p2 = 0;
    while (p1 < (int)cps.size() && p2 < (int)cop_events.size()) {
      if (cmp(cps[p1], cop_events[p2])) {
        so.push_back(cps[p1++]);
      }
      else {
        so.push_back(cop_events[p2++]);
      }
    }
    while (p1 < (int)cps.size()) {
      so.push_back(cps[p1++]);
    }

    while (p2 < (int)cop_events.size()) {
      so.push_back(cop_events[p2++]);
    }

    events = so;
    int p0 = 0;
    while (events[p0].second != 0) p0++;

    int l = p0, r = p0, sz = (int)events.size();

    while (events[(l + sz - 1) % sz].second != -1) l = (l + sz - 1) % sz;
    while (events[(r + 1) % sz].second != -1) r = (r + 1) % sz;

    for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
      if (events[j].second > 0) {
        cnt_good[events[j].second]++;
      }
    }
  }
  vector<int> sol;
  for (int i = 1; i <= c; i++) {
    if (cnt_good[i] == n) {
      sol.push_back(i);
    }
  }
  cout << (int)sol.size() << "\n";
  for (auto& i : sol) {
    cout << i << " ";
  }
  cout << "\n";
}

Compilation message

fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 9 ms 340 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 175 ms 340 KB Output is correct
5 Correct 39 ms 340 KB Output is correct
6 Correct 824 ms 524 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1129 ms 956 KB Output is correct
2 Correct 2531 ms 1996 KB Output is correct
3 Correct 2641 ms 1900 KB Output is correct
4 Correct 2600 ms 1836 KB Output is correct