【HDOJ6627】equation（模拟）

题意：给定n，整数序列a和b，整数C，求所有成立的x
n<=1e5，1<=a[i]<=1e3，-1e3<=b[i]<=1e3，1<=C<=1e9
思路：
大概就照每条直线的零点分段，维护一下系数和常数项
特判的地方挺多，精度也要注意，写起来像计算几何
感觉这种麻烦的东西应该有模板
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 #define N  1100000
 11 #define M  4100000
 12 #define fi first
 13 #define se second
 14 #define MP make_pair
 15 #define pi acos(-1)
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 18 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 19 #define lowbit(x) x&(-x)
 20 #define Rand (rand()*(1<<16)+rand())
 21 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 22 #define ls p<<1
 23 #define rs p<<1|1
 24 
 25 const ll MOD=998244353,inv2=(MOD+1)/2;
 26       double eps=1e-6;
 27       int INF=1e9;
 28 
 29 struct arr
 30 {
 31     ll a,b;
 32 }c[N],ans[N];
 33 
 34 bool cmp(arr a,arr b)
 35 {
 36     return a.b*b.a>b.b*a.a;
 37 }
 38 
 39 ll read()
 40 {
 41    ll v=0,f=1;
 42    char c=getchar();
 43    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 44    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 45    return v*f;
 46 }
 47 
 48 ll gcd(ll x,ll y)
 49 {
 50     if(y==0) return x;
 51     return gcd(y,x%y);
 52 }
 53 
 54 int xiaoyu(ll x1,ll y1,ll x2,ll y2)
 55 {
 56     //printf("xiaoyu %I64d %I64d %I64d %I64d
",x1,y1,x2,y2);
 57     int p=-1;
 58     ll t=x1*y2-y1*x2;
 59     if(t==0) return 1;
 60     if(t<0) p=-p;
 61     if(y1*y2<0) p=-p;
 62     return (p==1);
 63 }
 64 
 65 int main()
 66 {
 67     //freopen("1.in","r",stdin);
 68     int cas=read();
 69     while(cas--)
 70     {
 71         int n;
 72         scanf("%d",&n);
 73         ll C=read();
 74         rep(i,1,n)
 75         {
 76             c[i].a=read();
 77             c[i].b=read();
 78         }
 79         sort(c+1,c+n+1,cmp);
 80         //rep(i,1,n) printf("%I64d %I64d
",c[i].a,c[i].b);
 81         int m=0;
 82         ll sa=0,sb=0;
 83         rep(i,1,n)
 84         {
 85             sa-=c[i].a;
 86             sb-=c[i].b;
 87         }
 88         //printf("sa=%I64d C-sb=%I64d
",sa,C-sb);
 89         int flag=0;
 90         if(sa==0&&C-sb==0) flag=1;
 91         if(xiaoyu(C-sb,sa,-c[1].b,c[1].a))
 92         {
 93             if(sa==0&&C-sb!=0) continue;
 94             m++;
 95             ll t=gcd(abs(C-sb),abs(sa));
 96             //printf("t=%I64d
",t);
 97             ans[m].a=(C-sb)/t;
 98             ans[m].b=sa/t;
 99             if(ans[m].b<0)
100             {
101                 ans[m].a=-ans[m].a;
102                 ans[m].b=-ans[m].b;
103             }
104         }
105         c[n+1].a=-1e15; c[n+1].b=1;
106         rep(i,1,n)
107         {
108             sa+=2ll*c[i].a;
109             sb+=2ll*c[i].b;
110             //printf("sa=%I64d C-sb=%I64d
",sa,C-sb);
111             if(sa==0&&C-sb==0)
112             {
113                 flag=1;
114                 break;
115             }
116             if(sa==0&&C-sb!=0) continue;
117             if(xiaoyu(C-sb,sa,-c[i].b,c[i].a)==0&&xiaoyu(C-sb,sa,-c[i+1].b,c[i+1].a))
118             {
119                 if(m>=1&&(C-sb)*ans[m].b==sa*ans[m].a) continue;
120                 m++;
121                 ll t=gcd(abs(C-sb),abs(sa));
122                 ans[m].a=(C-sb)/t;
123                 ans[m].b=sa/t;
124                 if(ans[m].b<0)
125                 {
126                     ans[m].a=-ans[m].a;
127                     ans[m].b=-ans[m].b;
128                 }
129             }
130         }
131         if(flag)
132         {
133             printf("-1
");
134             continue;
135         }
136         if(m==0)
137         {
138             printf("0
");
139             continue;
140         }
141 
142         printf("%d ",m);
143         rep(i,1,m-1) printf("%I64d/%I64d ",ans[i].a,ans[i].b);
144         printf("%I64d/%I64d
",ans[m].a,ans[m].b);
145     }
146 
147     return 0;
148 }