Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- typedef pair<int, int> ii;
- const int N = 1004, oo = 1e8;
- int n, orgN;
- ii a[N], orgArr[N];
- vector<ii> vec;
- void compress() {
- for (int i = 1; i <= n; ++i) {
- orgArr[i] = a[i];
- vec.push_back(a[i]);
- } orgN = n;
- sort(vec.begin(), vec.end());
- vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
- n = vec.size();
- for (int i = 1; i <= n; ++i) a[i] = vec[i-1];
- }
- bool cmp(ii a, ii b) { return a.first * b.second < a.second * b.first; }
- ii ans[N];
- vector<ii> More, Less;
- vector<int> Equal;
- void getRes(int id, int mul) {
- sort(More.begin(), More.end(), cmp);
- sort(Less.begin(), Less.end(), cmp); reverse(Less.begin(), Less.end());
- sort(Equal.begin(), Equal.end());
- int minVal = oo, maxVal = -oo;
- for (int i = 0; i < (int) More.size(); ++i) {
- int A = More[i].first, B = More[i].second;
- int l = 0, r = Less.size()-1, save = -1;
- while (l <= r) {
- int mid = (l + r) / 2;
- if (A * Less[mid].second < B * Less[mid].first) {
- save = mid; l = mid + 1;
- }
- else r = mid - 1;
- }
- minVal = min(minVal, i+1 + save+1);
- maxVal = max(maxVal, i+1 + save+1);
- }
- if (More.empty()) {
- minVal = 0;
- for (int i = 0; i < (int) Less.size(); ++i) {
- int A = Less[i].first, B = Less[i].second;
- if ( (A > 0 && B < 0) || (A < 0 && B > 0) ) break;
- maxVal++;
- }
- }
- for (int i = 0; i < (int) Equal.size(); ++i) {
- if (Equal[i] * mul < 0) minVal++, maxVal++;
- }
- ans[id].first = min(ans[id].first, minVal);
- ans[id].second = max(ans[id].second, maxVal);
- }
- void Process(int id, int mul) {
- More.clear(); Less.clear(); Equal.clear();
- for (int i = 1; i <= n; ++i) {
- if (id == i) continue;
- if (a[id].first > a[i].first) {
- if (mul == 1) More.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
- else Less.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
- }
- else if (a[id].first < a[i].first) {
- if (mul == 1) Less.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
- else More.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
- }
- else {
- Equal.push_back(a[id].second - a[i].second);
- }
- }
- getRes(id, mul);
- }
- void sol() {
- compress();
- for (int id = 1; id <= n; ++id) {
- ans[id] = ii(orgN-1, 1);
- Process(id, 1);
- cerr << "# ";
- cerr << n - ans[id].first << " " << n - ans[id].second << '\n';
- exit(0);
- }
- for (int id = 1; id <= orgN; ++id) {
- for (int i = 1; i <= n; ++i) if (orgArr[i] == a[i]) {
- cout << orgN - ans[i].first << " " << orgN - ans[i].second << '\n';
- break;
- }
- }
- /// a == 0 or b == 0 ??
- }
- #undef int
- int main() {
- #define int long long
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("ranking.inp", "r", stdin);
- //freopen("ranking.out", "w", stdout);
- freopen("input.txt", "r", stdin);
- cin >> n;
- for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
- sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement