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;
- struct ii {
- int X, Y;
- ii() {}; ii(int X, int Y) : X(X), Y(Y) {};
- };
- int getMul(ii a, ii b) {
- int tmp = (a.Y * b.Y < 0) ? -1 : 1;
- tmp *= (a.X*b.Y - a.Y*b.X);
- return (tmp < 0) ? -1 : 1;
- }
- bool operator < (const ii a, const ii b) { return getMul(a, b) < 0; }
- bool operator > (const ii a, const ii b) { return getMul(a, b) > 0; }
- bool operator <= (const ii a, const ii b) { return getMul(a, b) <= 0; }
- bool operator >= (const ii a, const ii b) { return getMul(a, b) >= 0; }
- const int N = 1004, oo = 1e8;
- int n;
- ii a[N];
- vector<ii> lsMore, lsLess, lsEqual;
- int resMax, resMin;
- void process(int id) {
- lsMore.clear(); lsLess.clear(); lsEqual.clear();
- for (int i = 1; i <= n; ++i) {
- if (i == id) continue;
- ii tmp = ii(a[id].Y - a[i].Y, a[id].X - a[i].X);
- if (tmp.Y == 0) lsEqual.push_back(tmp);
- if (tmp.Y > 0) lsMore.push_back(tmp);
- if (tmp.Y > 0) lsLess.push_back(tmp);
- }
- sort(lsMore.begin(), lsMore.end());
- sort(lsLess.begin(), lsLess.end());
- int Add = 0;
- for (int i = 0; i < (int) lsEqual.size(); ++i) {
- ii frac = lsEqual[i];
- Add += (frac.X <= 0);
- }
- /// all < lsMore[0] ???
- lsMore.push_back(ii(oo, 1));
- for (int i = 0; i < (int) lsMore.size()-1; ++i) {
- ii frac1 = lsMore[i], frac2 = lsMore[i+1];
- int Lmost = lsLess.size(), Rmost = lsLess.size();
- int l = 0, r = lsLess.size()-1;
- while (l <= r) {
- int mid = (l + r) / 2; ii frac = lsLess[mid];
- if (frac >= frac2) r = mid - 1;
- else if (frac < frac1) l = mid + 1;
- else {
- Rmost = mid; l = mid + 1;
- }
- }
- l = 0, r = lsLess.size()-1;
- while (l <= r) {
- int mid = (l + r) / 2; ii frac = lsLess[mid];
- if (frac >= frac2) r = mid - 1;
- else if (frac < frac1) l = mid + 1;
- else {
- Lmost = mid; r = mid - 1;
- }
- }
- resMax = max(resMax, i+1 + (int) lsLess.size()-1 - Lmost + 1 + Add);
- resMin = min(resMin, i+1 + (int) lsLess.size()-1 - Rmost + 1 + Add);
- }
- }
- void sol() {
- for (int i = 1; i <= n; ++i) {
- resMax = -oo, resMin = oo;
- process(i);
- cout << n - resMax << " " << n - resMin << '\n';
- }
- }
- #undef int
- int main() {
- #define int long long
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- if (fopen("input.txt", "r")) {
- freopen("input.txt", "r", stdin);
- }
- cin >> n;
- for (int i = 1; i <= n; ++i) cin >> a[i].X >> a[i].Y;
- sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement