icontofig | 发布于 2019-08-05 22:56:27 | 阅读量 341 | 思维题

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int p[maxn],q[maxn];
int tot = 0;
struct funct{
int a,b;
double k;
}f[maxn];
const double eps = 1e-5;
bool cmp(funct x,funct y){
return x.k - y.k >= eps;
}
int T;
int n;
int suma,sumb;
int c;
int x,y,g;
bool flag;
double xx,yy;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&c);
tot = 0;
suma = 0;
sumb = 0;
for(int i = 1;i <= n;++i){
scanf("%d%d",&f[i].a,&f[i].b);
suma += f[i].a;
sumb += f[i].b;
f[i].k = double(-f[i].b) / double(f[i].a);
}
sort(f+1,f+n+1,cmp);
int j = 1;
flag = false;
for(int j = 1;j <= n;++j){
if(suma == 0 && sumb == c){
printf("-1\n");
flag = true;
break;
}
else{
if(suma != 0){
x = c - sumb;
y = suma;
xx = x;
yy = y;
if(j == 1){
if(xx / yy - f[j].k >= eps){
tot++;
p[tot] = x;q[tot] = y;
}
}
else{
if(xx / yy - f[j].k >= eps && xx / yy - f[j-1].k < eps){
tot++;
p[tot] = x;q[tot] = y;
}
}
}
suma -= 2*f[j].a;
sumb -= 2*f[j].b;
}
}
x = c - sumb;
y = suma;
if(y == 0 && x == 0 && !flag){
printf("-1\n");
flag = true;
}
if(flag)continue;
xx = x;
yy = y;
if(xx / yy - f[n].k < eps){
tot++;
p[tot] = x;q[tot] = y;
}
printf("%d",tot);
for(int i = tot;i >= 1;--i){
if(p[i] == 0){
printf(" 0/1");
}
else{
g = __gcd(p[i],q[i]);
p[i] /= g;q[i] /= g;
if(q[i] < 0){
q[i] = -q[i];
p[i] = -p[i];
}
printf(" %d/%d",p[i],q[i]);
}
}
printf("\n");
}
return 0;
}```

341 人读过

0 条评论