Advertisement
Hello_MMM

Untitled

Dec 15th, 2020
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct line {
  8.     int k, b;
  9.     bool x = false;
  10. };
  11.  
  12. bool Is3PointsOnLine(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {
  13.     if ((p2.first - p1.first) != 0 && (p2.second - p1.second) != 0) {
  14.         return ((p3.first - p1.first) / (p2.first - p1.first) == (p3.second - p1.second) / (p2.second - p1.second));
  15.     }
  16.     else {
  17.         //прямая вида x = a
  18.         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))
  19.             return true; //fix me
  20.         else
  21.             return false;
  22.     }
  23. }
  24.  
  25. bool Is4PointsOnLine(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4) {
  26.     if (Is3PointsOnLine(p2, p3, p4) && Is3PointsOnLine(p1, p3, p4) &&
  27.         Is3PointsOnLine(p1, p2, p4) && Is3PointsOnLine(p1, p2, p3)) {
  28.         return true;
  29.     }
  30.     return false;
  31. }
  32.  
  33. pair<bool, int> Is3of4PointsOnLine(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4) {
  34.     pair<bool, int> ans;
  35.     if (Is3PointsOnLine(p2, p3, p4)) {;
  36.         ans.first = true;
  37.         ans.second = 0;
  38.         return ans;
  39.     }
  40.     if (Is3PointsOnLine(p1, p3, p4)) {
  41.         ans.first = true;
  42.         ans.second = 1;
  43.         return ans;
  44.     }
  45.    
  46.     if (Is3PointsOnLine(p1, p2, p4)) {
  47.         ans.first = true;
  48.         ans.second = 2;
  49.         return ans;
  50.     }
  51.     if (Is3PointsOnLine(p1, p2, p3)) {
  52.         ans.first = true;
  53.         ans.second = 3;
  54.         return ans;
  55.     }
  56.     ans.first = false;
  57.     return ans;
  58. }
  59.  
  60. //лежит ли точка на прямой
  61. bool PointIsOnLine(line l, int x, int y) {
  62.     if (!l.x) {
  63.         if (y == ((l.k * x) + l.b))
  64.             return true;
  65.     }
  66.     else {
  67.         if (x == l.b)
  68.             return true;
  69.     }
  70.     return false;
  71. }
  72.  
  73. /*bool CheckPoint(pair<int, int> p) {
  74.     bool smt = false;
  75.     for (int e = 0; e < lines.size(); e++) {
  76.         if (PointIsOnLine({ lines[e].k, lines[e].b }, p.first, p.second)) {
  77.             lines[e].count++;
  78.             smt = true;
  79.         }
  80.     }
  81.  
  82.     return smt;
  83. }*/
  84.  
  85. //составляем уравнение прямой
  86. line f(pair<int, int> c1, pair<int, int> c2) {
  87.     int x1 = c1.first;
  88.     int y1 = c1.second;
  89.     int x2 = c2.first;
  90.     int y2 = c2.second;
  91.  
  92.     line ans;
  93.     if (x2 != x1) {
  94.         ans.k = (y2 - y1) / (x2 - x1);//fix
  95.         ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
  96.         ans.x = false;
  97.     }
  98.     else {
  99.         ans.k = 0;     
  100.         ans.b = x1;
  101.         ans.x = true;
  102.     }
  103.  
  104.     return ans;
  105. }
  106.  
  107. int main() {
  108.     int n;
  109.     cin >> n;
  110.     vector<pair<int, int>> p(n);
  111.  
  112.     vector<int> not_used;
  113.  
  114.     for (int i = 0; i < n; i++)
  115.         cin >> p[i].first >> p[i].second;
  116.    
  117.     if (n < 5) {
  118.         cout << "yes";
  119.     }
  120.     else {
  121.         vector<line> lines;
  122.  
  123.         pair<bool, int> needs = Is3of4PointsOnLine(p[0], p[1], p[2], p[3]);
  124.  
  125.         if (Is4PointsOnLine(p[0], p[1], p[2], p[3])) {
  126.             lines.push_back(f(p[0], p[1]));
  127.  
  128.             pair<int, int> e = {-8, -8};
  129.             //тут мы подбираем вторую линию
  130.             for (int i = 4; i < n; i++) {
  131.                 if (!PointIsOnLine(lines[0], p[i].first, p[i].second)) {
  132.                     if (e.first == -8) {
  133.                         e.first = i;
  134.                     }
  135.                     else if (e.second == -8) {
  136.                         e.second = i;
  137.  
  138.                         lines.push_back(f(p[e.first], p[e.second]));
  139.                     }
  140.                     else {
  141.                         cout << "no";
  142.                         return 0;
  143.                     }
  144.                 }
  145.             }
  146.  
  147.             cout << "yes";
  148.             return 0;
  149.         }
  150.         else if (needs.first) {
  151.             pair<int, int> e = { needs.second, -8 };
  152.             vector<int> d = { 0,1,2,3 };
  153.             d.erase(d.begin() + needs.second);
  154.             lines.push_back(f(p[d[0]], p[d[1]]));
  155.  
  156.             //тут мы подбираем вторую линию
  157.             for (int i = 4; i < n; i++) {
  158.                 if (e.second == -8) {
  159.                     if (!PointIsOnLine(lines[0], p[i].first, p[i].second)) {
  160.                         if (e.second == -8) {
  161.                             e.second = i;
  162.                             lines.push_back(f(p[e.first], p[e.second]));
  163.                         }
  164.                         else if (!PointIsOnLine(lines[1], p[i].first, p[i].second)) {
  165.                             cout << "no";
  166.                         }
  167.                     }
  168.                 }
  169.             }
  170.  
  171.             cout << "yes";
  172.             return 0;
  173.         }
  174.         else {
  175.             //01 23
  176.             lines = {};
  177.             lines.push_back(f(p[0], p[1]));
  178.             lines.push_back(f(p[2], p[3]));
  179.  
  180.             bool asdfasdf = false;
  181.             for (int i = 4; i < n; i++) {
  182.                 if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
  183.                     asdfasdf = true;
  184.                     break;
  185.                 }
  186.             }
  187.             if (!asdfasdf) {
  188.                 cout << "yes";
  189.                 return 0;
  190.             }
  191.  
  192.  
  193.             //02 13
  194.             lines = {};
  195.             lines.push_back(f(p[0], p[2]));
  196.             lines.push_back(f(p[1], p[3]));
  197.  
  198.             asdfasdf = false;
  199.             for (int i = 4; i < n; i++) {
  200.                 if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
  201.                     asdfasdf = true;
  202.                     break;
  203.                 }
  204.             }
  205.             if (!asdfasdf) {
  206.                 cout << "yes";
  207.                 return 0;
  208.             }
  209.  
  210.             //03 12
  211.             lines = {};
  212.             lines.push_back(f(p[0], p[3]));
  213.             lines.push_back(f(p[1], p[2]));
  214.  
  215.  
  216.             asdfasdf = false;
  217.             for (int i = 4; i < n; i++) {
  218.                 if (!PointIsOnLine(lines[0], p[i].first, p[i].second) && !PointIsOnLine(lines[1], p[i].first, p[i].second)) {
  219.                     asdfasdf = true;
  220.                     break;
  221.                 }
  222.             }
  223.             if (!asdfasdf) {
  224.                 cout << "yes";
  225.                 return 0;
  226.             }
  227.  
  228.             cout << "no";
  229.         }
  230.        
  231.     }
  232.  
  233.     return 0;
  234. }
  235.  
  236. /*5
  237. 2 1
  238. 3 3
  239. 2 0
  240. 3 2
  241. 3 1*/
  242. /*6
  243. 2 1
  244. 3 3
  245. 2 0
  246. 3 2
  247. 3 1
  248. 3 0*/
  249.  
  250. /*5
  251. 1 1
  252. 2 1
  253. 3 1
  254. 2 2
  255. 4 2*/
  256.  
  257. /*6
  258. 1 1
  259. 2 1
  260. 3 1
  261. 2 2
  262. 4 2
  263. 4 1*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement