QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466796#8468. Collinear ArrangementsLRWA 0ms3792kbC++144.5kb2024-07-08 10:07:142024-07-08 10:07:14

Judging History

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

  • [2024-07-08 10:07:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-07-08 10:07:14]
  • 提交

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;
    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;
    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 root = 1;

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

            ii XY = {y.ff-x.ff, x.ss-y.ss};
            ii normal_vec = {-XY.ss, XY.ff};
            ii root2 = {a[root].ff - normal_vec.ff, a[root].ss - normal_vec.ss};
            int ans = -1;
            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]);
                if ((Up && Right) || (Down && Right) || (Down && Left)) {
                    ans = v;
                    l = mid + 1;
                }
                else r = mid - 1;
            }

            if (ans == -1) cout << -1 << '\n';
            else {
                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);
//                cout << u << " -> " << v << '\n';
                cout << res << '\n';
            }
        }
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 3792kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

1000 1
-139438978 -172098481
-125097652 -169056403
155419484 -28898293
186215972 6874955
240691742 77644763
334255616 236444333
342049790 274206233
342049766 274611851
342049472 275025569
342049298 275242193
342048794 275724449
341967248 297262013
341966000 297569423
341963012 298092233
341960624 29...

output:

-1

result:

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