QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#961768 | #6864. Fencing the cows | Da_Capo | AC ✓ | 637ms | 6632kb | C++20 | 3.5kb | 2025-04-02 14:57:50 | 2025-04-02 14:57:57 |
Judging History
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