Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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";
- }
- 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 {
- cout << "no";
- return 0;
- }
- }
- }
- cout << "yes";
- 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[1], p[i].first, p[i].second)) {
- cout << "no";
- }
- }
- }
- }
- 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;
- }
- /*5
- 2 1
- 3 3
- 2 0
- 3 2
- 3 1*/
- /*6
- 2 1
- 3 3
- 2 0
- 3 2
- 3 1
- 3 0*/
- /*5
- 1 1
- 2 1
- 3 1
- 2 2
- 4 2*/
- /*6
- 1 1
- 2 1
- 3 1
- 2 2
- 4 2
- 4 1*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement