Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cstdio>
- #include <vector>
- #include <map>
- #include <set>
- #include <cstring>
- #include <queue>
- #include <bitset>
- using namespace std;
- #define eps 0.000001
- #define Pi acos(-1)
- struct point{
- double x, y;
- point(){}
- point(double _x, double _y) {
- x = _x;
- y = _y;
- }
- };
- int n;
- point p[200000];
- double vec(point a, point b) {
- return a.x * b.y - a.y * b.x;
- }
- bool operator <(const point a, const point b) {
- return atan2(a.y, a.x) < atan2(b.y, b.x);
- }
- long long l[200000], r[200000];
- long long d[200000];
- int main() {
- // freopen("tricount.in", "r", stdin);freopen("tricount.out", "w", stdout);
- cin >> n;
- for (int i = 0; i < n; i++) {
- scanf("%lf %lf", &p[i].x, &p[i].y);
- }
- if (n == 5) {
- // cout << 5 << endl;
- // return 0;
- }
- sort(p, p + n);
- for (int i = n; i < 2 * n; i++) {
- // cout << p[i - n].x << ' ' << p[i - n].y << endl;
- p[i] = p[i - n];
- }
- int r1 = 0;
- for (int i = 0; i < n; i++) {
- r1 = max(r1, i);
- while (r1 - i < n - 1 && abs(atan2(p[r1 + 1].y, p[r1 + 1].x) - atan2(p[i].y, p[i].x)) < Pi) {
- r1++;
- }
- r[i] = r1 - i;
- r[i + n] = r[i];
- //cout << r[i] << endl;
- d[i] = (i > 0 ? d[i - 1]: 0) + r[i];
- }
- for (int i = 0; i < n; i++) {
- d[i + n] = d[i + n - 1] + r[i];
- }
- int l1 = 2 * n - 1;
- for (int i = 2 * n - 1; i >= n; i--) {
- l1 = min(l1, i);
- while (i - l1 < n - 1 && abs(atan2(p[l1 - 1].y, p[l1 - 1].x) - atan2(p[i].y, p[i].x)) < Pi) {
- l1--;
- }
- l[i] = i - l1;
- l[i - n] = l[i];
- //cout << l[i] << endl;
- }
- //cout << "popka" << endl;
- long long k = 0;
- long long ans = 0;
- for (long long i = 0; i < n; i++) {
- //cout << i << endl;
- k = max(k, (long long)i + 1);
- while (k <= i + r[i]) {
- int t = k + r[k];
- if (t >= n) {
- t -= (t / n) * n;
- }
- int t1 = i - l[i + n];
- if (t1 < 0) {
- t1 = n + t1 - 1;
- }
- // cout << t << endl;
- if (t >= t1) {
- break;
- }
- k++;
- }
- if (k > i + r[i]) {
- continue;
- }
- long long t1 = i - l[i + n];
- if (t1 < 0) {
- t1 = n + t1 - 1;
- }
- //cout << k << endl;
- long long k1 = k;
- if (k1 >= n) {
- k1 -= n;
- }
- if (k >= n && t1 < n) {
- t1 += n;
- }
- long long k2 = k;
- if (i + r[i] >= n && k < n) {
- k2 += n;
- }
- long long t2 = t1;
- if (i + r[i] >= n && t1 < n) {
- t2 += n;
- }
- long long p = 0;
- if (i + r[i] < n && k >= n) {
- p += n;
- }
- long long s = max(0LL, r[k] - k + t1 - (min(i + r[i] + p, i - 1LL + n) - k2 + 1));
- // cout << s << endl;
- // cout << d[min(i + r[i], i - 1LL + n)] - (k > 0 && k != n ? d[k - 1]: 0) << endl;
- ans += d[min(i + r[i] + p, i - 1LL + n)] - (k > 0 && k != n ? d[k - 1]: 0) - (abs(r[k] - k + t1) * (abs(r[k] - k + t1) + 1)) / 2 + (s * (s + 1)) / 2;
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement