QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466813#8468. Collinear ArrangementsLRWA 0ms3632kbC++145.0kb2024-07-08 10:20:482024-07-08 10:20:49

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 10:20:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2024-07-08 10:20:48]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 2e5 + 5;
int n, q;
ii a[maxn];

inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

inline int rand(int l, int r)
{
    uniform_int_distribution<int> rg(l, r);
    return rg(rng);
}


/**
    A, B, C collinear
    when
    (Ax - Bx) / (Ay - By) == (Bx - Cx) / (By - Cy)

**/

bool cw(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans > 0;
}

bool ccw(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans < 0;
}

bool collinear(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans == 0;
}

void inc(int &x) {
    x++;
    if (x > n) x -= n;
}

int inc2(int x, int y) {
    x += y;
    if (x > n) x -= n;
    return x;
}

bool binsearch(int u, int v, ii x, ii y) {
    if (u >= v) v += n;
    int l = u; int r = v - 1;
    if (cw(x, y, a[l])) swap(x, y);
    while (l <= r) {
        int mid = (l + r) / 2;
        if (collinear(x, y, a[mid])) return 1;
        if (ccw(x, y, a[mid])) l = mid + 1;
        else r = mid - 1;
    }
    return 0;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> q;
    int _q = q;
    for (int i = 1; i <= n; i++)
        cin >> a[i].ff >> a[i].ss,
        a[i + n] = a[i];
    while (q--)
    {
        int t; ii x, y;
        cin >> t;
        if (t == 1)
        {
            cin >> x.ff >> x.ss;
            int ans = 0;
            for (int i = 1; i <= n; i++)
            {
                int l = i + 1, r = i + n - 1, yes = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (cw(a[i], x, a[mid])) l = mid + 1;
                    else if (ccw(a[i], x, a[mid])) r = mid - 1;
                    else
                    {
                        yes = mid;
                        break;
                    }
                }
                l = i + 1, r = i + n - 1;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (cw(a[i], x, a[mid])) r = mid - 1;
                    else if (ccw(a[i], x, a[mid])) l = mid + 1;
                    else
                    {
                        yes = mid;
                        break;
                    }
                }
                ans += yes > 0;
            }
            cout << ans / 2 << "\n";
        }
        else
        {
            cin >> x.ff >> x.ss >> y.ff >> y.ss;
            int u, ans;
            while (true) {

                int root = rand(1, n);



                while (collinear(a[root], x, y)) inc(root);
                u = root;
                int l = 1; int r = n - 1;
                if (cw(x, y, a[root])) swap(x, y);

                ii XY = {y.ff-x.ff, y.ss-x.ss};
                ii normal_vec = {-XY.ss, XY.ff};
                ii root2 = {a[root].ff - normal_vec.ff, a[root].ss - normal_vec.ss};
                ans = -1;
//                cout << normal_vec.ff<<','<<normal_vec.ss<<'\n';
//                cout << root2.ff<<','<<root2.ss<<'\n';
                while (l <= r) {
                    int mid = (l + r) / 2;
                    int v = inc2(u, mid);
                    bool Up = !cw(a[root], root2, a[v]);
                    bool Down = !ccw(a[root], root2, a[v]);
                    bool Left = !cw(x, y, a[v]);
                    bool Right = !ccw(x, y, a[v]);
//                    cout << v << " := " << Up << ' ' << Down << ' ' << Left << ' ' << Right << '\n';
                    if ((Up && Right) || (Down && Right) || (Down && Left)) {
                        ans = v;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                if (ans != -1) break;
            }
            int v = ans; int res = 0;
            if (u == v) res = binsearch(u, v, x, y);
            else res = binsearch(u, v, x, y) + binsearch(v, u, x, y);
            if (_q == 1) {
                 cout << u << " -> " << v << '\n';
                 vector <int> tmp;
                 for (int i = 1; i <= n; i++) if (collinear(a[i], x, y)) tmp.push_back(i);
                 for (int i : tmp) cout << i << " : "; cout << '\n';
            }
            cout << res << '\n';
        }
    }
}

/**
5 1
0 0
2 0
2 1
1 2
0 2
2 1 1 2 2
**/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

5 3
0 0
2 0
2 1
1 2
0 2
1 1 1
2 1 1 2 2
1 2 2

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3632kb

input:

3 1
0 0
1 0
0 1
2 1 1 2 2

output:

2 -> 1
1 : 
1

result:

wrong answer 1st numbers differ - expected: '1', found: '2'