解法
部分問題: 直線 \(l\) を固定したとき
直線\(l: ax + by = c\) で,平面が2つの領域に分割される. 2点 \(P,Q\) が,同じ領域に属しているかを判定する. 同じなら直線を通らなくて済むし, 異なるなら直線を通らないといけない. 2つの領域は \(ax + by > c\) と \(ax + by < c\) に分けられるので, これで判定ができる.
本問題
通らなくて良い直線のコストを 0で置き直して コスト全体をソートして,小さい方から \(K\) 個選ぶのが最適.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,k;
cin >> n >> k;
pll p,q;
cin >> p.first >> p.second;
cin >> q.first >> q.second;
vll ws;
rep(i,n){
ll a,b,c,w; cin >> a >> b >> c >> w;
auto f = [=](pll r) -> bool {
auto [x,y] = r;
return a*x + b*y > c;
};
if(f(p) ^ f(q) == 0) w = 0;
ws.emplace_back(w);
}
sort(all(ws));
ll ans = 0;
rep(i,k) ans += ws[i];
cout << ans << endl;
return 0;
}