Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <string>
  6. #include <set>
  7. #include <cstdio>
  8. #include <iomanip>
  9. #include <map>
  10. #include <stdio.h>
  11. #include <math.h>
  12. #include <queue>
  13. #include <random>
  14. #define and &&
  15. #define or ||
  16. using namespace std;
  17. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  18.  
  19. #define PI acos(-1.0)
  20. using namespace std;
  21. const long long inf = 1e10;
  22. const long long m = 1e9 + 7;
  23. const long double e = 0.0000001;
  24.  
  25. int gcd(int a, int b) { return b ? a : gcd(b, a % b); }
  26.  
  27. int toNum(char s) {
  28. return s - 'a';
  29. }
  30.  
  31.  
  32. double S(int x1, int y1, int x2, int y2) {
  33. return abs(x1 * y2 - y1 * x2) / 2.0;
  34. }
  35.  
  36. int f(double a, double b, double c, double x, double y) {
  37. double k = a * x + b * y + c;
  38. if (k > 0)
  39. return 1;
  40. else if (k < 0)
  41. return -1;
  42. else if (k == 0)
  43. return 0;
  44. }
  45.  
  46. bool isCrossing(double x1, double y1, double x2, double y2, double x11, double y11, double x22, double y22)
  47. {
  48. double a1 = y2 - y1;
  49. double b1 = -(x2 - x1);
  50. double c1 = -x1 * (y2 - y1) + y1 * (x2 - x1);
  51. double a2 = y22 - y11;
  52. double b2 = -(x22 - x11);
  53. double c2 = -x11 * (y22 - y11) + y11 * (x22 - x11);
  54. double pos1 = f(a1, b1, c1, x11, y11);
  55. double pos2 = f(a1, b1, c1, x22, y22);
  56. double pos3 = f(a2, b2, c2, x1, y1);
  57. double pos4 = f(a2, b2, c2, x2, y2);
  58. if (!((x1 == x2 and y1 == y2) or (x11 == x22 and y11 == y22))) {
  59. if (!(c2 * a1 == a2 * c1 and b1 * a2 == b2 * a1 and c1 * b2 == c2 * b1)) {
  60. if (pos1 != pos2 and pos3 != pos4) {
  61. return true;
  62. }
  63. else {
  64. return false;
  65. }
  66. }
  67. else {
  68. if (x1 == x2 and x2 == x11 and x11 == x22) {
  69. if ((min(y1, y2) <= y11 and y11 <= max(y1, y2)) or (min(y1, y2) <= x22 and y22 <= max(y1, y2))) {
  70. return true;
  71. }
  72. else {
  73. return false;
  74. }
  75. }
  76. else if ((min(x1, x2) <= x11 and x11 <= max(x1, x2)) or (min(x1, x2) <= x22 and x22 <= max(x1, x2))) {
  77. return true;
  78. }
  79. else {
  80. return false;
  81. }
  82. }
  83. }
  84. else {
  85. if (x1 == x2 and y1 == y2) {
  86. if (f(a2, b2, c2, x1, y1) == 0) {
  87. return true;
  88. }
  89. else {
  90. return false;
  91. }
  92. }
  93. else if (x11 == x22 and y11 == y22) {
  94. if (f(a1, b1, c1, x11, y11) == 0) {
  95. return true;
  96. }
  97. else {
  98. return false;
  99. }
  100.  
  101. }
  102. }
  103. }
  104.  
  105.  
  106.  
  107. double len(vector<double>gg) {
  108. return pow((gg[0] * gg[0] + gg[1] * gg[1]), 0.5);
  109. }
  110.  
  111. bool isRight(vector<double>first, vector<double>second) {
  112. double ans = first[0] * second[0] + first[1] * second[1];
  113. if (abs(ans) < e)
  114. return true;
  115. else
  116. return false;
  117. }
  118.  
  119.  
  120. double ax, bx, cx, dx, ay, by, cy, dy;
  121. vector <double> ab(2);
  122. vector <double> ac(2);
  123. vector <double> dc(2);
  124. vector <double> db(2);
  125.  
  126. void input() {
  127. cin >> ax >> ay;
  128. cin >> bx >> by;
  129. cin >> dx >> dy;
  130. cin >> cx >> cy;
  131. ab[0] = bx - ax;
  132. ab[1] = by - ay;
  133. ac[0] = cx - ax;
  134. ac[1] = cy - ay;
  135. dc[0] = cx - dx;
  136. dc[1] = cy - dy;
  137. db[0] = bx - dx;
  138. db[1] = by - dy;
  139. }
  140.  
  141. void solve() {
  142. if ((isCrossing(ax, ay, bx, by, cx, cy, dx, dy) || isCrossing(ax, ay, cx, cy, bx, by, dx, dy)))
  143. cout << "self-intersecting polyline";
  144. else if (!(isCrossing(ax, ay, dx, dy, bx, by, cx, cy)))
  145. cout << "non-convex polygon";
  146. else if (abs(len(ab) - len(dc)) < e && abs(len(ab) - len(db)) < e && abs(len(ac) - len(dc)) < e && isRight(ab, ac) && isRight(dc, db))
  147. cout << "square";
  148. else if (abs(len(ab) - len(dc)) < e && abs(len(ab) - len(db)) < e && abs(len(ac) - len(dc)) < e)
  149. cout << "rhombus";
  150. else if (isRight(ab, ac) && isRight(dc, db))
  151. cout << "rectangle" << "\n";
  152. else if (abs(ab[0] * dc[1] - ab[1] * dc[0]) < e && abs(ac[0] * db[1] - ac[1] * db[0]) < e)
  153. cout << "parallelogram";
  154. else if (abs(ab[0] * dc[1] - ab[1] * dc[0]) < e || abs(ac[0] * db[1] - ac[1] * db[0]) < e)
  155. cout << "trapezoid";
  156. else
  157. cout << "convex polygon";
  158. }
  159.  
  160. int main() {
  161. IOS;
  162. input();
  163. solve();
  164. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement