牛客挑战赛60 B题数据有锅
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const int N = 2050;
const int inf = 1e9;
//const ll inf = 1e18;
const ll mod = 998244353;//1e9 + 7;
int n, m, k;
int vis[N][N];
pii a[N * N];
void sol()
{
cin >> n >> m >> k;
n <<= 1, m <<= 1;
for(int i = 0; i <= n; i++)
for(int j = 0; j<= m; j++)
vis[i][j] = 0;
for(int i = 1; i <= k; i++)
cin >> a[i].fi >> a[i].sc;
k = min(k, 3000);
for(int i = 1; i <= k; i++)
a[i].fi <<= 1, a[i].sc <<= 1;
for(int i = 1; i <= k; i++)
{
for(int j = i + 1; j <= k; j++)
{
++vis[(a[i].fi + a[j].fi) / 2][(a[i].sc + a[j].sc) / 2];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(vis[i][j] >= 2)
{
cout << "YES ";
cout << fixed << setprecision(1) << 1.0 * i / 2 << ' ' << 1.0 * j / 2 << '\n';
return;
}
}
}
cout << "NO" << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while(tt--)
sol();
}
spj有问题，上面这个做法如果在得到最早可行的解直接break出来会判对，但是这样最后扫一遍的写法就会判错（有些是答案的点被判成不是答案了）。
直接break：（AC）
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const int N = 2050;
const int inf = 1e9;
//const ll inf = 1e18;
const ll mod = 998244353;//1e9 + 7;
int n, m, k;
int vis[N][N];
pii a[N * N];
void sol()
{
cin >> n >> m >> k;
n <<= 1, m <<= 1;
for(int i = 0; i <= n; i++)
for(int j = 0; j<= m; j++)
vis[i][j] = 0;
for(int i = 1; i <= k; i++)
cin >> a[i].fi >> a[i].sc;
k = min(k, 3000);
for(int i = 1; i <= k; i++)
a[i].fi <<= 1, a[i].sc <<= 1;
int x = 0, y = 0;
for(int i = 1; i <= k; i++)
{
for(int j = i + 1; j <= k; j++)
{
++vis[(a[i].fi + a[j].fi) / 2][(a[i].sc + a[j].sc) / 2];
x = (a[i].fi + a[j].fi) / 2;
y = (a[i].sc + a[j].sc) / 2;
if(vis[x][y] > 1)
{
break;
}
}
if(vis[x][y] > 1)
break;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(vis[i][j] >= 2)
{
cout << "YES ";
cout << fixed << setprecision(1) << 1.0 * i / 2 << ' ' << 1.0 * j / 2 << '\n';
return;
}
}
}
cout << "NO" << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while(tt--)
sol();
} 出题人谢罪
