| 123456 |
- #include <algorithm>
- #include <iostream>
- #include <limits>
- #include <vector>
- using namespace std;using i128=__int128_t;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){long long n,k,x,y;cin>>n>>k>>x>>y;vector<long long>px(n+1),py(n+1);for(int i=0;i<n;++i){long long a,b;cin>>a>>b;px[i+1]=px[i]+a;py[i+1]=py[i]+b;}const i128 INF=(i128(1)<<120);i128 best=INF;for(int r=0;r<n;++r){i128 low=0,high=INF;for(int sx:{-1,1})for(int sy:{-1,1}){i128 A=i128(sx)*(x-px[r])+i128(sy)*(y-py[r]);i128 B=-i128(sx)*px[n]-i128(sy)*py[n];i128 C=B-i128(k)*n,R=i128(k)*r-A;if(C==0){if(R<0)low=1,high=0;}else if(C>0){if(R<0)low=1,high=0;else high=min(high,R/C);}else if(R<0){i128 need=(-R+(-C)-1)/(-C);low=max(low,need);}}if(low<=high)best=min(best,low*n+r);}if(best==INF)cout<<-1<<'\n';else cout<<(long long)best<<'\n';}}
|
