digits 2
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
You are given a positive integer n which is at most 100.
Please find a positive integer satisfying the following conditions:
1. The sum of all digits of this number is dividable by n.
2. This number is also dividable by n.
3. This number contains no more than 10410^4104 digits.
If such an integer doesn't exist, output "Impossible" (without quotation marks). If there are multiple such integers, please output any one.
输入描述:
The first line contains one integer T indicating that there are T tests.
Each test consists an integer n in a single line.
* 1≤T≤1001 \le T \le 1001≤T≤100
* 1≤n≤1001 \le n \le 1001≤n≤100
输出描述:
For each query, output one line containing the answer. The number you print cannot have leading zeros. If there are multiple answers, you can print any. If such an integer doesn't exist, output "Impossible" (without quotation marks) in a single line.
示例1
输入
3 1 9 12
输出
1 666666 888
说明
For the last test, 888 is dividable by 12 (888 = 12 * 74) and 8 + 8 + 8 = 24 is also dividable by 12 (24 = 12 * 2).
签到，输出n个n
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
void solve(){
scanf("%d",&n);
rep(i,1,n) printf("%d",n);
puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
generator 1
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
You are given four positive integers x0,x1,a,bx_0, x_1, a, bx0,x1,a,b. And you know xi=a⋅xi−1+b⋅xi−2x_i = a \cdot x_{i-1} + b \cdot x_{i-2}xi=a⋅xi−1+b⋅xi−2 for all i≥2i \ge 2i≥2.
Given two positive integers n, and MOD, please calculate xnx_nxn modulo MOD.
Does the problem look simple? Surprise! The value of n may have many many digits!
输入描述:
The input contains two lines.
The first line contains four integers x0,x1,a,bx_0, x_1, a, bx0,x1,a,b (1≤x0,x1,a,b≤1091 \le x_0, x_1, a, b \le 10^91≤x0,x1,a,b≤109).
The second line contains two integers n, MOD (1≤n<10(106),109<MOD≤2×1091 \le n < 10^{(10^6)}, 10^9 < MOD \le 2 \times 10^91≤n<10(106),109<MOD≤2×109, n has no leading zero).
输出描述:
Print one integer representing the answer.
示例1
输入
1 1 1 1 10 1000000001
输出
89
说明
The resulting sequence x is Fibonacci sequence. The 11-th item is 89.
示例2
输入
1315 521 20185 5452831 9999999999999999999999999999999999999 1000000007
输出
914730061
十进制矩阵快速幂练习题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
ll a,b,x0,x1,mod;
char n[maxn];
struct Matrix{
int a[3][3];
friend Matrix operator*(const Matrix&a,const Matrix&b){
Matrix c;memset(c.a,0,sizeof(c.a));
rep(i,1,2) rep(k,1,2) rep(j,1,2) c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod;
return c;
}
}c,ans;
void qpow(Matrix a,char *b){
int len=strlen(b+1);
dep(i,len,1){
int p=b[i]-'0';
Matrix tmp=a;
if(p) rep(j,1,p) ans=a*ans;
rep(j,1,9) a=a*tmp;
}
}
void solve(){
c.a[1][1]=a;c.a[1][2]=b;c.a[2][1]=1;c.a[2][2]=0;
ans.a[1][1]=ans.a[2][2]=1;ans.a[1][2]=ans.a[2][1]=0;
qpow(c,n);
printf("%lld\n",(ans.a[2][1]*x1%mod+ans.a[2][2]*x0%mod)%mod);
}
int main(){
scanf("%lld%lld%lld%lld%s%lld",&x0,&x1,&a,&b,n+1,&mod);
solve();
}
generator 2
时间限制：C/C++ 4秒，其他语言8秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
There is a sequence of length n: x0,x1,x2,…,xn−1x_0, x_1, x_2, \ldots, x_{n-1}x0,x1,x2,…,xn−1. Please answer Q queries. Each query consists of one integer v, asking the minimum index i such that xi=vx_i = vxi=v. If the sequence doesn't have any number with value v, you only need to output -1.
Does the problem look simple? Surprise! The value of n may be as large as 101810^{18}1018!
Because n is so large. We will only give you four integers x0,a,b,px_0, a, b, px0,a,b,p to generate the sequence. For all i>0, the sequence is generated as xi=(a⋅xi−1+b)mod px_i = (a \cdot x_{i-1} + b) \mod pxi=(a⋅xi−1+b)modp.
输入描述:
The first line of input contains an integer T (T≤4T \le 4T≤4) denoting there are T tests in the input.
Each test contains Q+2 lines.
The first line of each test contains five integers n,x0,a,b,pn, x_0, a, b, pn,x0,a,b,p (1≤n≤1018,0≤xp,a,b<p≤109+91 \le n \le 10^{18}, 0 \le x_p,a,b < p \le 10^9 + 91≤n≤1018,0≤xp,a,b<p≤109+9, p is a prime number).
The second line contains one integer Q (Q≤1000Q \le 1000Q≤1000).
Each of the following Q lines contains one integer v (0≤v<p0 \le v < p0≤v<p).
输出描述:
For each query, print one integer as the answer in one line.
示例1
输入
3 1000000009 1 1 1 1000000009 5 0 1 10 1000000008 1000000007 100000009 1 1 1 1000000009 3 0 10 1000000008 1000000000000000000 1 5 0 1000000007 6 0 1 10 1000000006 12345678 1234567
输出
1000000008 0 9 1000000007 1000000006 -1 9 -1 -1 0 381838283 500000003 652614354 581802189
说明
For the first test, the sequence looks like 1, 2, 3, ..., 1000000008, 0. So the position of the first occurrence of value v is v - 1 except for value 0 which occurs at 1000000008.
示例2
输入
2 1000000000000000000 5 2 2 1000000007 4 0 1 2 3 5 1 0 3 950000017 4 0 1 2 3
输出
115068150 342074 115068151 -1 -1 0 -1 1
在 a 不等于 0 的时候，xi 和 xi+1 是一对一对应的，所以可以直接套用 BSG 算法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int md;
int qp(int a,int b,int md){
int ret=1;
while(b){
if(b&1) ret=(1ll*ret*a)%(1ll*md);
a=1ll*a*a%(1ll*md);
b>>=1;
}
return ret;
}
unordered_map<int,int> mp;
int main(){
ll n;
int x,a,b,p;
int T;
scanf("%d",&T);
while(T--){
scanf("%lld%d%d%d%d",&n,&x,&a,&b,&p);
int q;
scanf("%d",&q);
md=p;
mp.clear();
int iv=1ll*b*qp(a-1,p-2,p)%(1ll*md);
int plu=qp(((1ll*x+1ll*iv)%md),p-2,p);
int sz=sqrt(p/(1ll*q)+1ll)+1;
int tmp=qp(a,sz,p);
int cnt=1;
int invb=qp(b,p-2,p);
int lim=sqrt(1ll*p*q)+1;
for(int i=1;i<=lim;i++){
cnt=(1ll*cnt*tmp)%(1ll*md);
if(!mp.count(cnt)) mp[cnt]=i;
}
for(int th=1;th<=q;th++){
int v;
scanf("%d",&v);
if(v==x){
printf("0\n");continue;
}
if(a==0 && v!=x){
if(v==b) printf("%d\n",1ll<n?1:-1);
else printf("-1\n");
continue;
}
if(a==1){
if(b==0) printf("-1\n");
else{
int ans=1ll*invb*(v-x+p)%(1ll*p);
printf("%d\n",1ll*ans<n?ans:-1);
}
continue;
}
ll mi=n;
int vv=1ll*(v+iv)%(1ll*md)*plu%(1ll*md);
int mul=1;
for(int i=0;i<=sz;i++){
int fg=(int)(1ll*vv*mul%(1ll*md));
if(mp.count(fg)){
mi=min(mi,1ll*mp[1ll*vv*mul%(1ll*md)]*sz-1ll*i);
}
mul=1ll*mul*a%(1ll*md);
}
if(mi==n){
printf("-1\n");
}
else{
printf("%lld\n",mi);
}
}
}
return 0;
}
independent set 1
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 102400K，其他语言204800K
64bit IO Format: %lld
题目描述
Note: For C++ languages, the memory limit is 100 MB. For other languages, the memory limit is 200 MB. In graph theory, an independent set is a set of nonadjacent vertices in a graph. Moreover, an independent set is maximum if it has the maximum cardinality (in this case, the number of vertices) across all independent sets in a graph.
An induced subgraph G'(V', E') of a graph G(V, E) is a graph that satisfies:
* V′⊆VV' \subseteq VV′⊆V
* edge (a,b)∈E′(a,b) \in E'(a,b)∈E′ if and only if a∈V′,b∈V′a \in V', b \in V'a∈V′,b∈V′, and edge (a,b)∈E(a, b) \in E(a,b)∈E;
Now, given an undirected unweighted graph consisting of n vertices and m edges. This problem is about the cardinality of the maximum independent set of each of the 2n2^n2n possible induced subgraphs of the given graph. Please calculate the sum of the 2n2^n2n such cardinalities.
输入描述:
The first line contains two integers n and m (2≤n≤26,0≤m≤n×(n−1)22 \le n \le 26, 0 \le m \le \frac{n \times (n-1)}{2}2≤n≤26,0≤m≤2n×(n−1)) --- the number of vertices and the number of edges, respectively. Next m lines describe edges: the i-th line contains two integers xi,yix_i, y_ixi,yi (0≤xi<yi<n0 \le x_i < y_i < n0≤xi<yi<n) --- the indices (numbered from 0 to n - 1) of vertices connected by the i-th edge.
The graph does not have any self-loops or multiple edges.
输出描述:
Print one line, containing one integer represents the answer.
示例1
输入
3 2 0 1 0 2
输出
9
说明
The cardinalities of the maximum independent set of every subset of vertices are: {}: 0, {0}: 1, {1}: 1, {2}: 1, {0, 1}: 1, {0, 2}: 1, {1, 2}: 2, {0, 1, 2}: 2. So the sum of them are 9.
示例2
输入
7 5 0 5 3 4 1 2 2 5 0 2
输出
328
我们可以用一个 n-bit 2 进制整数来表示一个点集，第 i 个 bit 是 1 就代表点集包含第 i 个点，若是 0 则不包含
每个点相邻的点也可以用一个 n-bit 2 进制整数表示，计做 ci，若第 i 个点和第 j 个点相邻，ci 的第 j 个 bit 是 1，否则是 0
记 x 的最低位且是 1 的 bit 的位置是 lbx
令 dp[x] 代表点集 x 的最大独立集 size，那么我们能够根据点 lbx 是否属于最大独立集来列出以下关系式：
dp[x] = max(dp[x - (1<lbx)], dp[x & (~clb_x)] + 1)
#include <bits/stdc++.h>
using namespace std;
char f[1<<26];
int n,m;
int b[30];
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(b,0,sizeof(b));
for(int i=1;i<=m;i++){
int f,t;
scanf("%d%d",&f,&t);
b[f]|=(1<<t);
b[t]|=(1<<f);
}
f[0]=0;
int ans=0;
for(int i=1;i<(1<<n);i++){
int x=0;
int cnt=(i&(-i));
while(cnt){
cnt>>=1;
x++;
}
x--;
f[i]=max((int)f[i-(1<<(x))],f[i-(i&b[x])-(1<<(x))]+1);
ans+=f[i];
}
printf("%d\n",ans);
}
return 0;
}
maximum clique 1
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
You are given a set S containing n distinct positive integers a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an.
Please find a subset of S which has the maximum size while satisfying the following constraint:
The binary representations of any two numbers in this subset must have at least two different bits.
If there are multiple valid subsets, please output any one of them.
输入描述:
The input contains only two lines.
The first line contains an integer N denoting the size of S.
The second line contains N positive integers a1,a2,…,aNa_1, a_2, \ldots, a_Na1,a2,…,aN denoting the members of set S.
* 1≤N≤50001 \le N \le 50001≤N≤5000
* 1≤ai≤1091 \le a_i \le 10^91≤ai≤109
* all aia_iai are distinct
输出描述:
You should output two lines.
The first line contains one integer m denoting the size of the subset you found.
The second line contains m positive integers denoting the member of this subset.
示例1
输入
5 3 1 4 2 5
输出
3 4 1 2
说明
3 (112) and 1 (012) has only 1 different bit so they can not be in the set together. 4 (1002) and 1 (0012) has 2 different bits so they can be in the set together.Following unordered pairs are allowed to be in the set together: <1, 2>, <1, 4>, <2, 4>, <2, 5>, <3, 4>, <3, 5>. Thus the maximum set is of size 3 ({1, 2, 4}).
二分图最大独立集的练习题
最大团问题和最大独立集问题是互补的问题
两个相异的数至少两个 bit 不一样的否命题就是 :
恰一个 bit 不一样
可发现按照题目叙述所建的图的补图就是刚好是二分图
于是套用二分图最大独立集模板就把这题解决了
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5010;
int n, m, k,p,t;
//bool mp[maxn][maxn];
int match[maxn],a[maxn],ma[maxn][32],used[maxn];
int judge(int x,int y){
int cnt=x^y;
cnt-=(cnt&(-cnt));
return cnt==0;
}
int kk(int u)
{
int t=0;
while (u)
{
t+=u%2;
u=u/2;
}
return t%2;
}
bool find(int u) {
used[u]=t;
for (int i=1;i<=ma[u][0];i++)
{
if (used[ma[u][i]]!=t) {
used[ma[u][i]] = t;
if (match[ma[u][i]] == -1 || find(match[ma[u][i]])) {
match[ma[u][i]] = u;
match[u] = ma[u][i];
return true;
}
}
}
return false;
}
int hungary() {
memset(match,-1,sizeof(match));
memset(used,0,sizeof(used));
int ans = 0;t=0;
for (int i=1;i<=n;i++)
if (kk(a[i]))
{
t++;
if (find(i)) ++ans;
}
t++;
for (int i=1;i<=n;i++)
if (kk(a[i])&&match[i]==-1)
{
find(i);
}
return ans;
}
int main()
{
memset(ma,0,sizeof(ma));
scanf("%d", &n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
if (judge(a[i],a[j])==1)
if (kk(a[i]))
{
ma[i][++ma[i][0]]=j;//ma[j][++ma[j][0]]=i;
} else ma[j][++ma[j][0]]=i;
printf("%d\n",n-hungary());
for(int i=1;i<=n;i++){
if (used[i]==t &&kk(a[i])) printf("%d ",a[i]);
if (used[i]!=t &&!kk(a[i])) printf("%d ",a[i]);
}
return 0;
}
subsequence 1
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
You are given two strings s and t composed by digits (characters '0' ∼\sim∼ '9'). The length of s is n and the length of t is m. The first character of both s and t aren't '0'.
Please calculate the number of valid subsequences of s that are larger than t if viewed as positive integers. A subsequence is valid if and only if its first character is not '0'. Two subsequences are different if they are composed of different locations in the original string. For example, string "1223" has 2 different subsequences "23".
Because the answer may be huge, please output the answer modulo 998244353.
输入描述:
The first line contains one integer T, indicating that there are T tests.
Each test consists of 3 lines.
The first line of each test contains two integers n and m, denoting the length of strings s and t.
The second line of each test contains the string s.
The third line of each test contains the string t.
* 1≤m≤n≤30001 \le m \le n \le 30001≤m≤n≤3000.
* sum of n in all tests ≤3000\le 3000≤3000.
* the first character of both s and t aren't '0'.
输出描述:
For each test, output one integer in a line representing the answer modulo 998244353.
示例1
输入
3 4 2 1234 13 4 2 1034 13 4 1 1111 2
输出
9 6 11
说明
For the last test, there are 6 subsequences "11", 4 subsequcnes "111" and 1 subsequence "1111" that are valid, so the answer is 11.
dp，s 的所有长度大于 m 且不以 0 开头的 subsequence 都大于 t，这部分可以枚举开头位置和子序列长度，套用组合公式计算。
s 长度等于 m 的 subsequence 部分使用动态规划计算：
令 dp (i, j) 表式 s 长度为 j 的后缀有多少 subsequence 长度为 i 且值大于 t 长度为 i 的后缀
可以根据 s 从后面数来第 j 个位数是否包含在 subsequence 内来列出 dp 式
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long md= 998244353;
int z,x,cas,c1[3010],c2[3010];
long long ans,n,m,w,h,f[3010],c[3010][3010],pre[3010][3010];
int main()
{
c[0][0]=1;
for(int i=1;i<=3000;i++){
c[i][0]=1,c[i][i]=1;
for(int j=1;j<i;j++)
{
c[i][j]=(c[i-1][j]+c[i-1][j-1])%md;
pre[i][j]=(pre[i][j-1]+c[i][j])%md;
}
pre[i][i]=(pre[i][i-1]+c[i][i])%md;
}
scanf("%d",&cas);
while (cas--)
{
ans=0;
scanf("%d%d",&z,&x);
getchar();
for (int i=1;i<=z;i++)
c1[i]=getchar()-'0';
getchar();
for (int i=1;i<=x;i++)
c2[i]=getchar()-'0';
memset(f,0,sizeof(f));
f[0]=1;
for (int i=1;i<=z;i++)
for (int j=x;j>=1;j--)
if (c1[i]>c2[j])
{
if (z-i>=x-j) ans=(ans+f[j-1]*c[z-i][x-j])%md;
} else
if (c1[i]==c2[j])
{
if (z-i>=x-j) f[j]=(f[j]+f[j-1])%md;
}
//printf("%lld\n",ans);
for (int i=1;i<=z;i++)
if (c1[i]&&z-i>=x) ans=((ans+pre[z-i][z-i]-pre[z-i][x-1])%md+md)%md;
printf("%lld\n",ans);
}
return 0;
}
subsequence 2
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
There is a hidden string of length n composed of the first m lowercase English letters. For any two different English letters, we will tell you a subsequence of the hidden string constructed by removing all other letters from the hidden string.
For example, if the hidden string is "apple" and the chosen letters are 'e' and 'p', the resulting subsequence would be "ppe"; if the chosen letters are 'a' and 'x', the resulting subsequence would be "a".
Now, please recover the hidden string. Output -1 if there are no possible hidden string. Output any one if there are multiple possible hidden strings.
输入描述:
The first line contains two integers n and m.
Following are m⋅(m−1)/2m \cdot (m-1)/2m⋅(m−1)/2 groups of two lines. The first line in each group contains a two-letter string composed of c1, c2, and an integer LEN. The second line contains a string composed of letters c1, c2 with length LEN, indicates the resulting subsequence by removing all other letters except c1 and c2 from the hidden string.
* 1≤n≤1041 \le n \le 10^41≤n≤104
* 2≤m≤102 \le m \le 102≤m≤10
* 0≤LEN≤n0 \le LEN \le n0≤LEN≤n
* all unordered pairs of letters in first m small English letters will occur exactly once.
输出描述:
If there is at least one possible hidden string, please output any. Otherwise, output -1.
示例1
输入
3 3 ab 2 ab bc 2 bc ca 2 ac
输出
abc
说明
First group tells us that there is one 'a' and one 'b' where 'a' is before 'b', the second group tells us there is one 'b' and one 'c' where 'b' is before 'c'. So the only possible answer is "abc" which satisfies the last group as well.
示例2
输入
3 3 cb 3 bbc ca 2 ac ab 3 abb
输出
-1
示例3
输入
4 3 ac 4 cccc ba 0 cb 4 cccc
输出
cccc
实际上若不是无解，可能答案就只有一种
记由左边数来第 i 个字符c 的位置为 posc,i，根据 Input ，我可以知道所有 posc,i 的大小关系
若把任两个字符所在的位置的大小关系都建出来，边数太多了
我们可以只建立 Input 中的字符串的相邻两个字符的位置大小关系即可
建完图后就套用拓扑排序模板即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,m;
char c[maxn],s[maxn];
void solve(){
map<char,int> mp;
int flag[27]={0,};
vector<pair<int,int> > vec;
vector<int> g[27];
rep(i,1,m*(m-1)/2){
int len;
scanf("%s%d",c,&len);
if(len){
scanf("%s",s);
rep(j,0,len-1) if(!flag[s[j]-'a']) mp[s[j]]++;
if(len) flag[s[0]-'a']=flag[s[len-1]-'a']=1;
if(len>=2&&s[0]!=s[len-1]){
vec.pb({s[0]-'a',s[len-1]-'a'});
g[s[0]-'a'].pb(s[len-1]-'a');
}
}
}
int sum=0,num=0,ff=0;
rep(i,0,25) if(mp['a'+i]) sum+=mp['a'+i],num++;
if(sum>n){puts("-1");return;}
if(sum<n) ff=1;
int ind[27]={0,};
for(auto it:vec) ind[it.second]++;
queue<int> q;
int p[27],pt=0;
while(!q.empty()) q.pop();
for(int i=0;i<=25;i++) if(flag[i]&&ind[i]==0) q.push(i),p[++pt]=i;
while(!q.empty()){
int x=q.front(); q.pop();
for(auto v:g[x]){
ind[v]--;
if(ind[v]==0){
++pt; p[pt]=v; q.push(v);
}
}
}
//printf("#%d %d",pt,num);
if(pt<num){puts("-1");return;}
rep(i,1,pt){
rep(j,1,mp[p[i]+'a']) printf("%c",p[i]+'a');
}
if(ff) rep(i,0,25) if(!mp[i+'a']){
rep(j,1,n-sum) printf("%c",i+'a');
break;
}
puts("");
}
int main(){
while(~scanf("%d%d",&n,&m)) solve();
}
three points 1
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
You are given five positive integers w, h, a, b, c. Please construct 3 points X, Y, Z in the 2-dimensional plane such that the distance between X and Y is a, the distance between X and Z is b, the distance between Y and Z is c. Furthermore, the x coordinates of all constructed points must be in the range [0, w], and the y coordinates of all constructed points must be in the range [0,h].
The value of the constructed coordinates X, Y, Z can be real numbers. The input guarantees that at least one solution exists.
输入描述:
The first line contains an integer T indicating there are T tests.
Each test consists of a single line containing five integers: w, h, a, b, c.
1≤w,h,a,b,c≤501 \le w, h, a, b, c \le 501≤w,h,a,b,c≤50
1≤T≤5×1041 \le T \le 5 \times 10^41≤T≤5×104
输出描述:
For each test, output one line containing six numbers, the first two numbers are the coordinate of X, the third and fourth numbers are the coordinate of Y, the last two numbers are the coordinate of Z. If there are multiple solutions, please output any one.
All absolute error within 1e−61e^{-6}1e−6 will be ignored.
示例1
输入
3 24 16 20 25 15 1 1 1 1 1 50 50 1 2 3
输出
0.000000000000 0.000000000000 12.000000000000 16.000000000000 24.000000000000 7.000000000000 0.000000000000 0.000000000000 0.500000000000 0.866025403784 1.000000000000 0.000000000000 1.000000000000 0.000000000000 0.000000000000 0.000000000000 3.000000000000 0.000000000000
说明
For the last test, the distance between (1, 0) and (0, 0) is 1, the distance between (1, 0) and (3, 0) is 2, and the distance between (0, 0) and (3, 0) is 3.
计算几何
两个观察：1. 若一个三角形能摆在一个矩形里，总是能经过平移使得三角形至少有一个顶点和矩形的顶点重叠，且三角形的顶点仍在矩形里
2. 重叠了三角形的某个顶点和矩形的某个顶点后，我们可以把该重叠的点当旋转轴，旋转三角形，使得三角形有另一个点恰好在矩形的某个边上
于是我们可以枚举三角形的哪个顶点和举行的顶点重叠，以及三角形另一个位在矩形边上的点是哪个，总是能枚举到一个完全落在矩形里面的三角形摆放位置
#include <bits/stdc++.h>
using namespace std;
#define X x
#define Y y
double w,h,a,b,c;
const double eps=9e-7;
double x[4],y[4];
int Check(double w,double h,double a,double b,double c){
double beta=acos((a*a+b*b-c*c)/(2*a*b));
double alpha;
if(a<eps+w) alpha=0.0;
else alpha=acos(w/a);
x[0]=0.0,y[0]=0.0;
x[1]=a*cos(alpha),y[1]=a*sin(alpha);
x[2]=b*cos(alpha+beta),y[2]=b*sin(alpha+beta);
if(x[2]>-eps && x[2]<eps+w && y[2]>-eps && y[2]<h+eps){
return 1;
}
else return 0;
}
int main()
{
int T, w, h, a, b, c, flip;
for (scanf("%d", &T); T; T --)
{
scanf("%d%d%d%d%d", &w, &h, &a, &b, &c);
for (flip = 0; flip < 2; flip ++)
{
if (Check(w, h, a, b, c))
break ;
if (Check(w, h, a, c, b))
{
swap(X[0], X[1]), swap(Y[0], Y[1]);
break ;
}
if (Check(w, h, b, a, c))
{
swap(X[1], X[2]), swap(Y[1], Y[2]);
break ;
}
if (Check(w, h, b, c, a))
{
double tx = X[0], ty = Y[0];
X[0] = X[1], Y[0] = Y[1];
X[1] = X[2], Y[1] = Y[2];
X[2] = tx, Y[2] = ty;
break ;
}
if (Check(w, h, c, a, b))
{
double tx = X[1], ty = Y[1];
X[1] = X[0], Y[1] = Y[0];
X[0] = X[2], Y[0] = Y[2];
X[2] = tx, Y[2] = ty;
break ;
}
if (Check(w, h, c, b, a))
{
swap(X[2], X[0]), swap(Y[2], Y[0]);
break ;
}
swap(w, h);
}
if (flip)
{
for (int i = 0; i < 3; i ++)
swap(X[i], Y[i]);
}
for (int i = 0; i < 3; i ++)
printf("%.9f %.9f%c", X[i], Y[i], i == 2 ? '\n' : ' ');
}
return 0;
}
