QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463058#8468. Collinear ArrangementsLRWA 1ms3560kbC++203.8kb2024-07-04 12:51:082024-07-04 12:51:08

Judging History

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

  • [2024-07-04 12:51:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3560kb
  • [2024-07-04 12:51:08]
  • 提交

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];

/**
    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;
}

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 >> x.ff >> x.ss;
        if (t == 1)
        {
            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
        {
            set<int> ans;
            cin >> y.ff >> y.ss;
            int l = 1, r = n;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (cw(x, y, a[mid])) l = mid + 1;
                else if (ccw(x, y, a[mid])) r = mid - 1;
                else
                {
                    ans.emplace(mid);
                    break;
                }
            }
            l = 1, r = n;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (cw(x, y, a[mid])) r = mid - 1;
                else if (ccw(x, y, a[mid])) l = mid + 1;
                else
                {
                    ans.emplace(mid);
                    break;
                }
            }
            l = 1, r = n;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (cw(y, x, a[mid])) l = mid + 1;
                else if (ccw(y, x, a[mid])) r = mid - 1;
                else
                {
                    ans.emplace(mid);
                    break;
                }
            }
            l = 1, r = n;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (cw(y, x, a[mid])) r = mid - 1;
                else if (ccw(y, x, a[mid])) l = mid + 1;
                else
                {
                    ans.emplace(mid);
                    break;
                }
            }
            cout << ans.size() << "\n";
        }
    }
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3532kb

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: 1ms
memory: 3560kb

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'