Ada the Ladybug works as farmer. Its season of cucumbers and she wants to harvest them. There lies many cucumbers all around her house. She wants to choose a direction and follow it until all cucumbers in that direction are collected. Lets consider Ada's house as centerpiece of whole universe, lying on [0,0]. The cucumbers are defined as lines on plane. No cucumber goes through Ada's house (and no cucumber touches it). How many cucumbers can Ada pick in one go if she chooses the best direction possible? Input The first line contains an integer T, the number of test-cases. Each test-case begins with an integer 1 ≤ N ≤ 105 Afterward N lines follow, with four integers -106 ≤ x1,y1,x2,y2 ≤ 106, the beginning and end of each cucumber. Each cucumber has positive length. Sum of all N over all test-cases won't exceed 106 Even though cucumber will not go through house, they might touch, intersect or overlap other cucumbers! Output For each test-case print one integer - the maximal number of cucumbers which could be picked if Ada chooses a direction and picks every cucumber lying in it.的代码

以下是参考代码，使用了 C++ STL 中的 sort 函数和双指针来实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const double EPS = 1e-9;

struct Vector {
    double x, y;
    double angle; // 极角
};

// 计算点 P 的极角
double polar_angle(double x, double y) {
    return atan2(y, x);
}

// 计算向量 AB 的极角
double polar_angle(double Ax, double Ay, double Bx, double By) {
    return atan2(By - Ay, Bx - Ax);
}

// 计算向量 AB 的长度
double length(double Ax, double Ay, double Bx, double By) {
    return hypot(Bx - Ax, By - Ay);
}

// 计算向量 AB 和向量 CD 的交点
bool intersection(double Ax, double Ay, double Bx, double By,
                  double Cx, double Cy, double Dx, double Dy,
                  double& Px, double& Py) {
    double d = (Bx - Ax) * (Dy - Cy) - (By - Ay) * (Dx - Cx);
    if (abs(d) < EPS) return false; // 平行或重合
    double t = ((Cx - Ax) * (Dy - Cy) - (Cy - Ay) * (Dx - Cx)) / d;
    Px = Ax + t * (Bx - Ax);
    Py = Ay + t * (By - Ay);
    return true;
}

// 将向量按照极角排序
bool cmp(const Vector& a, const Vector& b) {
    return a.angle < b.angle;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<Vector> cucumbers;
        for (int i = 0; i < N; ++i) {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            double len = length(x1, y1, x2, y2);
            double angle = polar_angle(x1, y1, x2, y2);
            cucumbers.push_back({x1, y1, angle});
            cucumbers.push_back({x2, y2, angle + (angle < 0 ? 2 * M_PI : 0)});
        }
        sort(cucumbers.begin(), cucumbers.end(), cmp);
        int ans = 0;
        int left = 0, right = 0;
        while (left < cucumbers.size()) {
            while (right < cucumbers.size() && cucumbers[right].angle - cucumbers[left].angle <= M_PI) {
                ++right;
            }
            ans = max(ans, right - left);
            ++left;
        }
        cout << ans << endl;
    }
    return 0;
}

这个算法的时间复杂度为 $O(n \log n)$，其中 $n$ 是黄瓜的数量。