fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. struct Point {
  7.     long long x, y;
  8.     bool operator<(const Point& other) const {
  9.         if (x != other.x) return x < other.x;
  10.         return y < other.y;
  11.     }
  12.     bool operator==(const Point& other) const {
  13.         return x == other.x && y == other.y;
  14.     }
  15. };
  16.  
  17. // Orijentacija: 0-kolinearne, 1-desno, 2-levo
  18. int orientation(Point p, Point q, Point r) {
  19.     long long val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  20.     if (val == 0) return 0;
  21.     return (val > 0) ? 1 : 2;
  22. }
  23.  
  24. // Provera da li tacka r leži na duži pq (uz pretpostavku kolinearnosti)
  25. bool onSegment(Point p, Point q, Point r) {
  26.     return r.x <= max(p.x, q.x) && r.x >= min(p.x, q.x) &&
  27.            r.y <= max(p.y, q.y) && r.y >= min(p.y, q.y);
  28. }
  29.  
  30. string solve() {
  31.     Point a, b, c, d;
  32.     if (!(cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y)) return "";
  33.  
  34.     int o1 = orientation(a, b, c);
  35.     int o2 = orientation(a, b, d);
  36.     int o3 = orientation(c, d, a);
  37.     int o4 = orientation(c, d, b);
  38.  
  39.     // 1. Opšti slucaj: seku se u jednoj tacki (unutrašnji presek)
  40.     if (((o1 > 0 && o2 > 0 && o1 != o2) || (o1 == 0 || o2 == 0)) &&
  41.         ((o3 > 0 && o4 > 0 && o3 != o4) || (o3 == 0 || o4 == 0))) {
  42.  
  43.         // Provera kolinearnosti (svi o su 0)
  44.         if (o1 == 0 && o2 == 0 && o3 == 0 && o4 == 0) {
  45.             // Svedemo duži na uredene parove (manja tacka, veca tacka)
  46.             if (b < a) swap(a, b);
  47.             if (d < c) swap(c, d);
  48.  
  49.             // Pronalazimo presek intervala na pravoj
  50.             Point max_start = max(a, c);
  51.             Point min_end = min(b, d);
  52.  
  53.             if (max_start == min_end) return "jedna";
  54.             if (max_start < min_end) return "vise";
  55.             return "nema";
  56.         }
  57.  
  58.         // Ako nisu sve kolinearne, a seku se, to je jedna tacka
  59.         return "jedna";
  60.     }
  61.  
  62.     return "nema";
  63. }
  64.  
  65. int main() {
  66.     string result = solve();
  67.     if (result != "") cout << result << endl;
  68.     return 0;
  69. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/UqUhXk
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!