БЛОГ НА HUSL


Расстановка точек на прямые

Автор вопроса: asdfjsldfksjdsdjklas

Дано N, точек с заданными координатами, можно ли провести не более двух прямых так, чтобы все точки лежали хотя бы на одной из двух прямых?

Пример 1

Ввод:

6
0 1
1 1
2 1
0 2
1 3
2 2

Вывод:

no

Пример 2

Ввод:

6
2 2
4 6
1 0
2 1
6 1
1 1

Вывод:

yes

Вот мой код:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct line {
    int k, b;
    bool x = false;
};

bool Is3PointsOnLine(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {
    if ((p2.first - p1.first) != 0 && (p2.second - p1.second) != 0) {
        return ((p3.first - p1.first) / (p2.first - p1.first) == (p3.second - p1.second) / (p2.second - p1.second));
    }
    else {
        //прямая вида x = a
        if ((p2.first == p1.first && p2.second == p1.second) || (p2.first == p1.first && p2.first == p3.first) || (p2.second == p1.second && p2.second == p3.second))
            return true; //fix me
        else
            return false;
    }
}

bool Is4PointsOnLine(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4) {
    if (Is3PointsOnLine(p2, p3, p4) && Is3PointsOnLine(p1, p3, p4) &&
        Is3PointsOnLine(p1, p2, p4) && Is3PointsOnLine(p1, p2, p3)) {
        return true;
    }
    return false;
}

pair<bool, int> Is3of4PointsOnLine(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4) {
    pair<bool, int> ans;
    if (Is3PointsOnLine(p2, p3, p4)) {;
        ans.first = true;
        ans.second = 0;
        return ans;
    } 
    if (Is3PointsOnLine(p1, p3, p4)) {
        ans.first = true;
        ans.second = 1;
        return ans;
    }
    
    if (Is3PointsOnLine(p1, p2, p4)) {
        ans.first = true;
        ans.second = 2;
        return ans;
    }
    if (Is3PointsOnLine(p1, p2, p3)) {
        ans.first = true;
        ans.second = 3;
        return ans;
    }
    ans.first = false;
    return ans;
}

//лежит ли точка на прямой
bool PointIsOnLine(line l, int x, int y) {
    if (!l.x) {
        if (y == ((l.k * x) + l.b))
            return true;
    }
    else {
        if (x == l.b)
            return true;
    }
    return false;
}

/*bool CheckPoint(pair<int, int> p) {
    bool smt = false;
    for (int e = 0; e < lines.size(); e++) {
        if (PointIsOnLine({ lines[e].k, lines[e].b }, p.first, p.second)) {
            lines[e].count++;
            smt = true;
        }
    }

    return smt;
}*/

//составляем уравнение прямой
line f(pair<int, int> c1, pair<int, int> c2) {
    int x1 = c1.first;
    int y1 = c1.second;
    int x2 = c2.first;
    int y2 = c2.second;

    line ans;
    if (x2 != x1) {
        ans.k = (y2 - y1) / (x2 - x1);//fix
        ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
        ans.x = false;
    }
    else {
        ans.k = 0;      
        ans.b = x1;
        ans.x = true;
    }

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);

    vector<int> not_used;

    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
    
    if (n < 5) {
        cout << "yes";
        cout << "adsdas";
        return 0;
    }
    else {
        vector<line> lines;

        pair<bool, int> needs = Is3of4PointsOnLine(p[0], p[1], p[2], p[3]);

        if (Is4PointsOnLine(p[0], p[1], p[2], p[3])) {
            lines.push_back(f(p[0], p[1]));

            pair<int, int> e = {-8, -8};
            //тут мы подбираем вторую линию
            for (int i = 4; i < n; i++) {
                if (!PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                    if (e.first == -8) {
                        e.first = i;
                    }
                    else if (e.second == -8) {
                        e.second = i;

                        lines.push_back(f(p[e.first], p[e.second]));
                    }
                    else if (!PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                        cout << "no";
                        return 0;
                    }
                }
            }

            if (lines.size() == 2) {
                cout << "yes";
            }
            else {
                cout << "no";
            }
            
            return 0;
        }
        else if (needs.first) {
            pair<int, int> e = { needs.second, -8 };
            vector<int> d = { 0,1,2,3 };
            d.erase(d.begin() + needs.second);
            lines.push_back(f(p[d[0]], p[d[1]]));

            //тут мы подбираем вторую линию
            for (int i = 4; i < n; i++) {
                if (e.second == -8) {
                    if (!PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                        if (e.second == -8) {
                            e.second = i;
                            lines.push_back(f(p[e.first], p[e.second]));
                        }                       
                    }
                }
                else if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                    cout << "no";
                    return 0;
                }
            }

            cout << "yes";
            return 0;
        }
        else {
            //01 23
            lines = {};
            lines.push_back(f(p[0], p[1]));
            lines.push_back(f(p[2], p[3]));

            bool asdfasdf = false;
            for (int i = 4; i < n; i++) {
                if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                    asdfasdf = true;
                    break;
                }
            }
            if (!asdfasdf) {
                cout << "yes";
                return 0;
            }


            //02 13
            lines = {};
            lines.push_back(f(p[0], p[2]));
            lines.push_back(f(p[1], p[3]));

            asdfasdf = false;
            for (int i = 4; i < n; i++) {
                if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                    asdfasdf = true;
                    break;
                }
            }
            if (!asdfasdf) {
                cout << "yes";
                return 0;
            }

            //03 12
            lines = {};
            lines.push_back(f(p[0], p[3]));
            lines.push_back(f(p[1], p[2]));


            asdfasdf = false;
            for (int i = 4; i < n; i++) {
                if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                    asdfasdf = true;
                    break;
                }
            }
            if (!asdfasdf) {
                cout << "yes";
                return 0;
            }

            cout << "no";
        }
        
    }

    return 0;
}

Но он выдает ошибку на 7-ом тесте, входные данные мне неизвестны. Помогите пожалуйста исправить ошибку

Я попытался сделать с тремя точками, вот код:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct line {
    int k, b;
    bool x = false;
    long long c = 0;
};
//лежит ли точка на прямой
bool PointIsOnLine(line l, int x, int y) {
    if (!l.x) {
        if (y == ((l.k * x) + l.b))
            return true;
    }
    else {
        if (x == l.b)
            return true;
    }
    return false;
}
//составляем уравнение прямой
line f(pair<int, int> c1, pair<int, int> c2) {
    int x1 = c1.first;
    int y1 = c1.second;
    int x2 = c2.first;
    int y2 = c2.second;
    line ans;
    if (x2 != x1) {
        ans.k = (y2 - y1) / (x2 - x1);//fix
        ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
        ans.x = false;
        ans.c = 2;
    }
    else {
        ans.k = 0;      
        ans.b = x1;
        ans.x = true;
        ans.c = 2;
    }
    return ans;
}
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    vector<int> not_used;
    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
    
    if (n < 5) {
        cout << "yes";
        return 0;
    }
    else {
        //
        vector<line> lines;
        lines.push_back(f(p[0], p[1]));
        pair<int, int> e = { -8, -8 };
        for (int i = 2; i < n; i++) {
            if (PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                lines[0].c++;
            }
            else if (e.first == -8) {
                e.first = i;
            }
            else if (e.second == -8) {
                e.second = i;
                lines.push_back(f(p[e.first], p[e.second]));
            }
            else if (PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                lines[1].c++;
            }
            else if (!PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                break;
            }
        }
        if (lines[0].c + lines[1].c == n) {
            cout << "yes";
            return 0;
        }
        lines = {};
        lines.push_back(f(p[0], p[2]));
        lines.push_back(f(p[1], p[2]));
        for (int i = 3; i < n; i++) {
            if (PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                lines[0].c++;
            }
            else if (PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                lines[0].c++;
            }
            else if (!PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                cout << "no";
                return 0;
            }
        }
        if (lines[0].c + lines[1].c == n)
            cout << "yes";
    }
    return 0;
}

Но ведь вариант с тремя точками не будет работать, если все точки будут расположены на двух параллельных прямых

Попробовал еще раз переделать, теперь валится на 5-ом тесте:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct line {
    int k, b;
    bool x = false;
    long long c = 0;
};

//лежит ли точка на прямой
bool PointIsOnLine(line l, int x, int y) {
    if (!l.x) {
        if (y == ((l.k * x) + l.b))
            return true;
    }
    else {
        if (x == l.b)
            return true;
    }
    return false;
}

//составляем уравнение прямой
line f(pair<int, int> c1, pair<int, int> c2) {
    int x1 = c1.first;
    int y1 = c1.second;
    int x2 = c2.first;
    int y2 = c2.second;

    line ans;
    if (x2 != x1) {
        ans.k = (y2 - y1) / (x2 - x1);//fix
        ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
        ans.x = false;
        ans.c = 0;
    }
    else {
        ans.k = 0;      
        ans.b = x1;
        ans.x = true;
        ans.c = 0;
    }

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);

    vector<int> not_used;

    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
    
    if (n < 5) {
        cout << "yes";
        return 0;
    }
    else {
        //
        vector<line> lines;

        for (int p1 = 0; p1 <= 2; p1++) {
            for (int p2 = 0; p2 <= 2; p2++) {
                if (p2 != p1) {
                    for (int p3 = 0; p3 < 4; p3++) {
                        if ((p3 != p1) && (p3 != p2)) {
                            for (int p4 = 0; p4 < 4; p4++) {
                                if ((p4 != p1) && (p4 != p2) && (p4 != p3)) {
                                    //cout << p1 << p2 << p3 << p4 << "\n";

                                    vector<int> not_used;
                                    pair<int, int> e = { -8, -8 };

                                    //строим прямые
                                    lines = {};
                                    lines.push_back(f(p[p1], p[p2]));
                                    lines.push_back(f(p[p3], p[p4]));

                                    for (int i = 0; i < n; i++) {
                                        if (PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                                            lines[0].c++;
                                        }
                                        else if (PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                                            lines[1].c++;
                                        }
                                        else if (e.first == -8) {
                                            e.first = i;
                                        }
                                        else if (e.second == -8) {
                                            e.second = i;
                                            lines.push_back(f(p[e.first], p[e.second]));
                                            lines[2].c = 2;

                                            for (int j = 0; j <= 3; j++) {
                                                if (PointIsOnLine(lines[2], p[j].first, p[j].second)) {
                                                    lines[2].c++;
                                                }
                                            }
                                        }
                                        else if (PointIsOnLine(lines[2], p[i].first, p[i].second)) {
                                            lines[1].c++;
                                        }
                                        else {
                                            not_used.push_back(i);
                                        }
                                    }

                                    if (e.first != -8 && e.second == -8) {
                                        not_used.push_back(e.first);
                                    }

                                    if (not_used.size() > 0) {
                                        if (not_used.size() >= 2) {
                                            lines.push_back(f(p[not_used[0]], p[not_used[1]]));
                                            for (int j = 0; j < not_used.size(); j++) {
                                                if (PointIsOnLine(lines[lines.size()-1], p[not_used[j]].first, p[not_used[j]].second)) {
                                                    lines[lines.size()-1].c++;
                                                }
                                            }
                                        }
                                        else {
                                            for (int i = 0; i <= 3; i++) {
                                                lines.push_back(f(p[not_used[0]], p[i]));
                                                lines[lines.size() - 1].c = 1;
                                                for (int j = 0; j <= 3; j++) {
                                                    if (PointIsOnLine(lines[lines.size()-1], p[j].first, p[j].second)) {
                                                        lines[lines.size()-1].c++;
                                                    }
                                                }
                                            }
                                        }
                                    }

                                    for (int counter1 = 0; counter1 < lines.size(); counter1++) {
                                        for (int counter2 = 0; counter2 < lines.size(); counter2++) {
                                            if (counter1 != counter2 && lines[counter1].c + lines[counter2].c >= n) {
                                                cout << "yes";
                                                return 0;
                                            }
                                        }
                                    }
                
                                }
                            }
                        }
                    }
                }
            }
        }

        cout << "no";
    }

    

    return 0;
}

Источник

Ответы (0 шт):

licensed under cc by-sa 3.0 with attribution.