[2015 HIAST Collegiate Programming Contest] 题解（AK）
简单的题或者我队友ac的题目没有写思路，只贴了代码，
自己ac的题目把题意和思路都说了一下，也贴上了代码。
[A - Who is the winner?]
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t;
int a[5],b[5];
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;--t){
for(int i=1;i<=3;i++){
cin>>a[i];
}
for(int i=1;i<=3;i++){
cin>>b[i];
}
int st=0;
for(int i=1;i<=3;i++){
if(a[i]<b[i]){
st=1;
break;
}else if(b[i]<a[i]){
st=-1;
break;
}
}
if(st==1){
cout<<"Player1\n";
}else if(st==-1)cout<<"Player2\n";
else cout<<"Tie\n";
}
return 0;
}
[B - New Job]
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t,n,m;
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n>>m;
int now=1,ans=0;
while(n){
now=min(now,m);
if(n<=now){
ans++;
break;
}
n-=now;
ans++;
now*=2;
}
cout<<ans<<'\n';
}
return 0;
}
[C - Palindrome Again !!]
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int t,n,p;
char s[N];
int main(){
ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>t;
while(t--){
cin>>n>>p;
cin>>s;
--p;
if(p>=n/2) p=(n-p-1+n)%n;
int ret=0,l=inf,r=-inf;
for(int i=0;i<n/2;i++){
int cost=(s[i]-s[n-i-1]+26)%26;
cost=min(cost,26-cost);
ret+=cost;
if(cost){
l=min(l,i);
r=max(r,i);
}
}
int ans=ret;
if(ret==0){
cout<<0<<'\n';
continue;
}
if(p>=r){
ans+=p-l;
}else if(p>=l){
ans+=min(p-l,r-p)+r-l;
}else{
ans+=r-p;
}
cout<<ans<<'\n';
}
return 0;
}
D. Time to go back
题意：
你有\(\mathit n\)个礼物，每个礼物的价格是\(a_i\),你准备给\(\mathit m\)个朋友买礼物，其中\(\mathit k\)个朋友的礼物价格必须大于等于\(\mathit d\)
问你有多少中购买礼物的方案。
思路：
容斥一下，先不考虑那\(\mathit k\)个朋友，一共有\(C(n,m)\)种方案，
我们记\(cnt\)为价格大于等于\(\mathit d\)的礼物个数。
然后减去不合法的方案数，他们是\(\sum_{i=0}^{i=k-1}C(cnt,i)*C(n-cnt,m-i)\)
注意过程中要取模即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
const ll mod = 1e9 + 7;
ll fac[maxn], inv[maxn];
void pre()
{
fac[0] = 1;
for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
inv[maxn - 1] = powmod(fac[maxn - 1], mod - 2, mod);
for (int i = maxn - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(int a, int b)
{
if (b > a || b < 0) return 0;
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int a[maxn];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
pre();
int t;
t = readint();
while (t--)
{
int n, m, k, d;
n = readint();
m = readint();
k = readint();
d = readint();
repd(i, 1, n)
{
a[i] = readint();
}
if (m > n)
{
printf("0\n");
continue;
}
int cnt = 0;
repd(i, 1, n)
{
if (a[i] >= d)
{
cnt++;
}
}
if (cnt < k)
{
printf("0\n");
continue;
}
ll ans = C(n, m);
repd(i, 0, k - 1)
{
ans = ans - C(cnt, i) * C(n - cnt, m - i) % mod + mod;
ans %= mod;
}
printf("%lld\n", ans );
}
return 0;
}
[E - Arrange Teams]
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n,m,t,P;
int vis[11][11],p[11],f[11][11];
int ans;
void dfs(int x,int y,int c,int cnt){
int res=(n-x)*m+m-y;
if(res<t-cnt) return;
if(x==n&&y==m){
if(cnt==t) ans++;
return;
}
int dx=x,dy=y;
++dy;
if(dy==m+1){
dy=1;
++dx;
}
for(int i=0;i<=t;i++) if(!p[i]){
if(i==0) dfs(dx,dy,i,cnt);
else{
if(vis[f[dx-1][dy]][i]||vis[f[dx][dy-1]][i]) continue;
f[dx][dy]=i;
p[i]=1;
dfs(dx,dy,i,cnt+1);
f[dx][dy]=0;
p[i]=0;
}
}
}
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>T;
while(T--){
memset(vis,0,sizeof(vis));
ans=0;
cin>>n>>m>>t;
cin>>P;
while(P--){
int a,b;
cin>>a>>b;
vis[a][b]=vis[b][a]=1;
}
dfs(1,1,0,0);
rep(i,1,t){
f[1][1]=i;
p[i]=1;
dfs(1,1,i,1);
f[1][1]=0;
p[i]=0;
}
if(ans==0) cout<<"impossible\n";
else cout<<ans<<'\n';
}
return 0;
}
F - Contestants Ranking
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n;
string s[3];
string p[110];
int dis[110];
map<string,int>vis;
int tot;
vector<int>g[110];
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>T;
while(T--){
cin>>n;
tot=1;
vis.clear();
vis["Ahmad"]=1;
p[1]="Ahmad";
queue<int>q;
q.push(1);
while(n--){
cin>>s[0]>>s[1]>>s[2];
rep(i,0,2) if(!vis.count(s[i])){
vis[s[i]]=++tot;
p[tot]=s[i];
}
rep(i,0,2) rep(j,0,2) if(i!=j){
g[vis[s[i]]].pb(vis[s[j]]);
g[vis[s[j]]].pb(vis[s[i]]);
}
}
rep(i,1,tot) dis[i]=inf;
dis[1]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int x:g[u]){
int cost=1+dis[u];
if(cost<dis[x]){
dis[x]=cost;
q.push(x);
}
}
}
vector<pair<int,string> >ans;
for(int i=1;i<=tot;i++){
ans.pb(mp(dis[i],p[i]));
}
sort(ans.begin(), ans.end());
cout<<sz(ans)<<'\n';
for(auto it:ans){
if(it.fi==inf) cout<<it.se<<" "<<"undefined\n";
else cout<<it.se<<" "<<it.fi<<'\n';
}
rep(i,1,tot) g[i].clear();
}
return 0;
}
(G) The jar of divisors,
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int t,n;
int main() {
ios::sync_with_stdio(false);
for(cin>>t;t;t--){
cin>>n;
if(n==1)cout<<"Bob\n";
else cout<<"Alice\n";
}
return 0;
}
H. Special Palindrome
题意：
每组数据给定一个整数\(\mathit n\)，让你计算有多少个回文数组\(a_1,a_2,\dots,a_i\)满足：
\(\sum a_j=n\)
且回文的对称轴之前是单调不下降的，对称轴之后是单调不上升的。
思路：
记忆化搜索：
搜索函数:
dfs(int pos, int rm)
\(pos\) 为到了第几个数
\(rm\)为目前还剩下多大的数值。
\(a_i\)为当前搜索中序列中的第\(\mathit i\)个数。
对\(a_{pos-1},rm\)条件下对答案的贡献进行记忆化，可以很快地得出答案。
代码：
ll ans;
int a[maxn];
ll dp[300][300];
void dfs(int pos, int rm)
{
if (rm == 0)
{
ans++;
return ;
}
if (dp[a[pos - 1]][rm] != -1)
{
ans += dp[a[pos - 1]][rm];
return ;
}
ll res = ans;
if (rm >= a[pos - 1])
{
ans++;
}
for (int i = a[pos - 1]; i * 2 <= rm; ++i)
{
a[pos] = i;
dfs(pos + 1, rm - i * 2);
}
res = ans - res;
dp[a[pos - 1]][rm] = res;
}
int main()
{
// freopen("C:\\code\\output.txt","w",stdout);
memset(dp, -1, sizeof(dp));
a[0] = 1;
int i;
while (cin >> i)
{
if (i == 0)
break;
ans = 0ll;
dfs(1, i);
cout << ans << '\n';
}
return 0;
}
I. Mancala
题意：
对于两行每行\(\mathit n\)个数的数组，每个数都大于等于0.
一次操作为选择一个下方的行中的一个数字\(num\)，从他逆时针方向的下一个数字开始每个数加1，逆时针方向走一直加，直到加的个数等于\(num\)，
现在给定两行每行\(\mathit n\)个数的数组，以及一个操作的结束位置，
让你恢复这次操作之前的数组，如果不存在这样的数组，就输出不合法。
思路：
观察数据范围：
n(1 ≤ n ≤ 10000)
观察题目时限：
time limit per test 3 seconds
所以可以暴力枚举这次操作的起始位置，然后判断是否合法，时间复杂度\(O(n^2)\)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int n;
int x, y;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
int cas = 1;
while (~scanf("%d %d %d", &n, &x, &y))
{
if (n + x + y == 0)
break;
printf("Case %d:\n", cas );
cas++;
repd(i, 1, n)
{
a[i] = readint();
c[i] = a[i];
}
repd(i, 1, n)
{
b[i] = readint();
d[i] = a[i];
}
int isok = 1;
ll add = 0ll;
ll m;
if (x == 1)
{
m = b[1];
repd(i, 1, n)
{
m = min(m, b[i]);
}
add += m * n * 2;
repd(i, 1, n)
{
a[i] -= m;
b[i] -= m;
if (a[i] < 0)
{
isok = 0;
}
}
if (isok)
{
while (y <= n)
{
a[y]--;
y++;
add++;
}
y = n;
while (y >= 1)
{
if (b[y] == 0)
{
break;
} else
{
add++;
b[y]--;
y--;
}
}
repd(i, 1, n)
{
if (a[i] < 0)
{
isok = 0;
}
}
}
} else
{
isok = 0;
repd(j, 1, n)
{
if (j == 3)
{
j = 3;
}
m = b[j];
int flag = 1;
repd(i, 1, n)
{
c[i] = a[i] - m;
d[i] = b[i] - m;
if (c[i] < 0 || d[i] < 0) {
flag = 0;
break;
}
}
if (!flag)
{
continue;
}
add = m * 2 * n;
if (j > y)
{
repd(i, j + 1, n)
{
add++;
d[i]--;
}
repd(i, 1, y)
{
add++;
d[i]--;
}
repd(i, 1, n)
{
add++;
c[i]--;
}
repd(i, 1, n)
{
if (c[i] < 0 || d[i] < 0) {
flag = 0;
break;
}
}
if (flag)
{
isok = 1;
repd(i, 1, n)
{
a[i] = c[i];
b[i] = d[i];
}
y = j;
break;
}
} else
{
repd(i, j + 1, y)
{
add++;
d[i]--;
}
repd(i, 1, n)
{
if (c[i] < 0 || d[i] < 0) {
flag = 0;
break;
}
}
if (flag)
{
isok = 1;
repd(i, 1, n)
{
a[i] = c[i];
b[i] = d[i];
}
y = j;
break;
}
}
}
}
if (isok)
{
b[y] += add;
repd(i, 1, n)
{
printf("%lld%c", a[i], i == n ? '\n' : ' ' );
}
repd(i, 1, n)
{
printf("%lld%c", b[i], i == n ? '\n' : ' ' );
}
} else
{
printf("INVALID\n");
}
}
return 0;
}
当然也有\(O(n)\)的解法：
//#pragma comment(linker,"/STACK:16777216") /*16Mb*/
//#pragma comment(linker,"/STACK:33554432") /*32Mb*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <list>
#include <iomanip>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<char, char> PCC;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;
int n, r, c;
LL a[2][100000];
int main()
{
//freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false); cin.tie(0);
//srand(time(0));
//freopen("rooms.in", "r", stdin)
//freopen("rooms.out", "w", stdout);
int tst = 0;
while (cin >> n >> r >> c)
{
if (!n) break;
tst++;
cout << "Case " << tst << ":\n";
LL m = 1000000000;
FOR (i, 0, 2)
FOR (j, 0, n)
{
cin >> a[i][j];
m = min(m, a[i][j]);
}
FOR (i, 0, 2)
FOR (j, 0, n)
{
a[i][j] -= m - 1;
}
m--;
m *= 2 * n;
r--; c--;
bool ok = 1;
while (true)
{
//cout << r<<" "<<c<<" "<<a[r][c]<<endl;
if (a[r][c] == 0 && r == 1)
{
a[r][c] = m;
break;
}
if (a[r][c])
{
m++, a[r][c]--;
if (r == 1) c--;
else c++;
if (c == -1) r = c = 0;
if (c == n)
{
c = n - 1;
r++;
}
}
else
{
ok = 0;
break;
}
}
if (!ok) cout << "INVALID\n";
else
FOR (i, 0, 2)
{
FOR (j, 0, n) cout << a[i][j] << " ";
cout << "\n";
}
}
}
J. Polygons Intersection
题意：
两个凸多边形，求其面积交。
思路：
经典的计算几何模板题
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 100;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
const int maxisn = 100;
const double eps = 1e-6;
const double pi = acos(-1.0);
int dcmp(double x) {
if (x > eps) return 1;
return x < -eps ? -1 : 0;
}
struct Point {
double x, y;
Point() {
x = y = 0;
}
Point(double a, double b) {
x = a, y = b;
}
inline Point operator-(const Point &b)const {
return Point(x - b.x, y - b.y);
}
inline Point operator+(const Point &b)const {
return Point(x + b.x, y + b.y);
}
inline double dot(const Point &b)const {
return x * b.x + y * b.y;
}
inline double cross(const Point &b, const Point &c)const {
return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
}
};
Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d) {
double u = a.cross(b, c), v = b.cross(a, d);
return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}
double PolygonArea(Point p[], int n) {
if (n < 3) return 0.0;
double s = p[0].y * (p[n - 1].x - p[1].x);
p[n] = p[0];
for (int i = 1; i < n; ++ i)
s += p[i].y * (p[i - 1].x - p[i + 1].x);
return fabs(s * 0.5);
}
double CPIA(Point a[], Point b[], int na, int nb) { //ConvexPolygonIntersectArea
Point p[maxisn], tmp[maxisn];
int i, j, tn, sflag, eflag;
a[na] = a[0], b[nb] = b[0];
memcpy(p, b, sizeof(Point) * (nb + 1));
for (i = 0; i < na && nb > 2; ++ i) {
sflag = dcmp(a[i].cross(a[i + 1], p[0]));
for (j = tn = 0; j < nb; ++ j, sflag = eflag) {
if (sflag >= 0) tmp[tn ++] = p[j];
eflag = dcmp(a[i].cross(a[i + 1], p[j + 1]));
if ((sflag ^ eflag) == -2)
tmp[tn ++] = LineCross(a[i], a[i + 1], p[j], p[j + 1]);
}
memcpy(p, tmp, sizeof(Point) * tn);
nb = tn, p[nb] = p[0];
}
if (nb < 3) return 0.0;
return PolygonArea(p, nb);
}
double SPIA(Point a[], Point b[], int na, int nb) { //SimplePolygonIntersectArea
int i, j;
Point t1[4], t2[4];
double res = 0, if_clock_t1, if_clock_t2;
a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0];
for (i = 2; i < na; ++ i) {
t1[1] = a[i - 1], t1[2] = a[i];
if_clock_t1 = dcmp(t1[0].cross(t1[1], t1[2]));
if (if_clock_t1 < 0) std::swap(t1[1], t1[2]);
for (j = 2; j < nb; ++ j) {
t2[1] = b[j - 1], t2[2] = b[j];
if_clock_t2 = dcmp(t2[0].cross(t2[1], t2[2]));
if (if_clock_t2 < 0) std::swap(t2[1], t2[2]);
res += CPIA(t1, t2, 3, 3) * if_clock_t1 * if_clock_t2;
}
}
return fabs(res);
}
Point p1[maxn], p2[maxn];
Point p3[maxn], p4[maxn];
int n, m;
int main() {
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
repd(i, 0, n - 1)
{
cin >> p1[i].x >> p1[i].y;
}
repd(i, 0, m - 1)
{
cin >> p2[i].x >> p2[i].y;
}
double ans = SPIA(p1, p2, n, m);
cout << fixed << setprecision(4) << ans << endl;
}
return 0;
}
京公网安备 11010502036488号