QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#961768#6864. Fencing the cowsDa_CapoAC ✓637ms6632kbC++203.5kb2025-04-02 14:57:502025-04-02 14:57:57

Judging History

This is the latest submission verdict.

  • [2025-04-02 14:57:57]
  • Judged
  • Verdict: AC
  • Time: 637ms
  • Memory: 6632kb
  • [2025-04-02 14:57:50]
  • Submitted

answer

// #include <algorithm>
// #include <bitset>
// #include <cctype>
// #include <cerrno>
// #include <clocale>
// #include <cmath>
// #include <complex>
// #include <cstdio>
// #include <cstdlib>
// #include <cstring>
// #include <ctime>
// #include <deque>
// #include <exception>
// #include <fstream>
// #include <functional>
// #include <limits>
// #include <list>
// #include <map>
// #include <iomanip>
// #include <ios>
// #include <iosfwd>
// #include <iostream>
// #include <istream>
// #include <ostream>
// #include <queue>
// #include <set>
// #include <sstream>
// #include <stack>
// #include <stdexcept>
// #include <streambuf>
// #include <string>
// #include <utility>
// #include <vector>
// #include <cwchar>
// #include <cwctype>
#include <bits/stdc++.h>

#define int long long
// #define int __int128
#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define lowbit(x) ((x) & (-x))

using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, string> PIS;
typedef pair<ld, int> PDI;

const int N = 1e6 + 10, M = 1e3 + 10, INF = 1e18;
const double eps = 1e-15;
const int mod = 998244353;
// int mod = 1e9 + 7;

int n, m, k;
int dx[4] = {1, 0, 0, -1}, dy[4] = {0, -1, 1, 0};
int a[N], b[N], c[N];
// int a, b, c;
// double a, b, c;
char op;
int x, y, z, r;
// double x, y, z, r;
string s, s1, s2, str;
// vector<PII> v[N];

struct node
{
    int x, y;
} zl[510], cd[510];

int f[510][510]; // i号栅栏到j号栅栏能够连一条边

int cross(node A, node B) // 叉乘 A->B左转为正 逆时针为正
{
    return A.x * B.y - A.y * B.x;
}

void solve(int _)
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> zl[i].x >> zl[i].y;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> cd[i].x >> cd[i].y;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            f[i][j] = INF;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            node v1 = {zl[j].x - zl[i].x, zl[j].y - zl[i].y};
            int pd = 0;
            for (int k = 1; k <= m; k++)
            {
                node v2 = {cd[k].x - zl[i].x, cd[k].y - zl[i].y};
                if (cross(v1, v2) >= 0) // 草不在这条栅栏的右边,也就是里面
                {
                    pd = 1;
                    break;
                }
            }
            if (!pd)
            {
                // cout<<i<<" "<<j<<endl;
                f[i][j] = 1; // 这条栅栏连一条边
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }

    int mx = INF;
    for (int i = 1; i <= n; i++)
    {
        mx = min(mx, f[i][i]); // 凸包最后走完一圈到自己本身
    }
    cout << (mx == INF ? -1 : mx) << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // getp(1000000);

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(9);
    // getline(cin, s);

    // while (t--)
    for (int i = 1; i <= t; i++)
    {
        solve(i);
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 637ms
memory: 6632kb

input:

9
4 1
1 1
1 -1
-1 1
-1 -1
0 0
4 1
1 1
1 -1
-1 1
-1 -1
1 0
500 500
-17 6
-12 -117
29 -279
47 -350
59 -396
62 -403
114 -508
220 -674
222 -676
481 -907
667 -1068
830 -1195
1063 -1347
1125 -1384
1196 -1424
1271 -1462
1430 -1514
1522 -1540
1941 -1579
1996 -1581
2068 -1573
2071 -1572
4138 -4
4143 1
4145 6...

output:

4
-1
36
6
34
-1
77
-1
-1

result:

ok 9 lines