fork download
  1. /* AKSHAT SHARMA */
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. #define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
  5. #define mp make_pair
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define ll long long
  10. #define li long int
  11. #define MOD 1000000007
  12. #define MAX 1000000001
  13. #define rep(i,a,b) for(i=a;i<b;i++)
  14. #define reqp(i,a,b) for(i=a;i<=b;i++)
  15. #define ren for(i=0;i<n;i++)
  16. #define ALL(a) (a).begin(),(a).end()
  17. using namespace std;
  18. typedef pair<li,li>pii;
  19. li arr[4][2],brr[4][2];
  20. double s1,s2;
  21.  
  22. void getLine(double x1, double y1, double x2, double y2, double &a, double &b, double &c)
  23. {
  24. // (x- p1X) / (p2X - p1X) = (y - p1Y) / (p2Y - p1Y)
  25. a = y2 - y1;
  26. b = x2 - x1;
  27. c = x1 * y2 - x2 * y1;
  28. }
  29.  
  30. double dist1(double pct1X, double pct1Y, double pct2X, double pct2Y, double pct3X, double pct3Y)
  31. {
  32. double a, b, c;
  33. getLine(pct2X, pct2Y, pct3X, pct3Y, a, b, c);
  34. return abs(a * pct1X + b * pct1Y + c) / sqrt(a * a + b * b);
  35. }
  36.  
  37.  
  38. double dist(li x,li y,li a,li b){
  39. double t1,t2;
  40. t1=(x-a);
  41. t2=(y-b);
  42. return sqrt(t1*t1*1.0+t2*t2*1.0);
  43. }
  44.  
  45. void check(li x,li y){
  46. li i;
  47. double a,b;
  48. int flag=0;
  49.  
  50. rep(i,0,4){
  51. if(dist1(x*1.0,y*1.0,arr[i][0],arr[i][1],arr[(i+1)%4][0],arr[(i+1)%4][1])-s1>DBL_EPSILON)
  52. return ;
  53. }
  54. rep(i,0,4){
  55. if(dist1(x*1.0,y*1.0,brr[i][0],brr[i][1],brr[(i+1)%4][0],brr[(i+1)%4][1])-s2>DBL_EPSILON)
  56. return;
  57. }
  58.  
  59.  
  60. // cout<<x<<" "<<y<<"\n";
  61. cout<<"YES";
  62. exit(0);
  63.  
  64.  
  65.  
  66. }
  67.  
  68. int main()
  69. {
  70. #ifndef ONLINE_JUDGE
  71. freopen("input_file.txt", "r", stdin);
  72. //freopen("output_file.txt", "w", stdout);
  73. #endif
  74. li i,j,k,l,n,test_case;
  75. test_case=1;
  76. //cin>>test_case;
  77. while(test_case--){
  78. map<pii,int>m;
  79. li cnt=0;
  80.  
  81. rep(i,0,4){
  82. cin>>arr[i][0]>>arr[i][1];
  83. m[mp(arr[i][0],arr[i][1])]=1;
  84. }
  85. s1=dist(arr[0][0],arr[0][1],arr[1][0],arr[1][1]);
  86. rep(i,0,4){
  87. cin>>brr[i][0]>>brr[i][1];
  88. rep(j,0,4){
  89. if(abs(dist(arr[j][0],arr[j][1],brr[i][0],brr[i][1])+dist(arr[(j+1)%4][0],arr[(j+1)%4][1],brr[i][0],brr[i][1])-s1)<DBL_EPSILON){
  90. cout<<"YES";
  91. return 0;
  92. }
  93. }
  94. if(m[mp(brr[i][0],brr[i][1])]==1)
  95. cnt++;
  96. }
  97.  
  98. s2=dist(brr[0][0],brr[0][1],brr[1][0],brr[1][1]);
  99. // cout<<"SSDDKJDKJD\n";
  100. // cout<<s1<<" "<<s2<<"...\n\n\n";
  101. rep(i,0,4){
  102. //cin>>brr[i][0]>>brr[i][1];
  103. rep(j,0,4){
  104. if(abs(dist(brr[j][0],brr[j][1],arr[i][0],arr[i][1])+dist(brr[(j+1)%4][0],brr[(j+1)%4][1],arr[i][0],arr[i][1])-s2)<DBL_EPSILON){
  105. cout<<"YES";
  106. return 0;
  107. }
  108. }
  109. //
  110. }
  111.  
  112.  
  113. if(cnt==1){
  114. cout<<"YES";
  115. }else{
  116. for(i=-100;i<=100;i++){
  117. for(j=-100;j<=100;j++){
  118. check(i,j);
  119. }
  120. }
  121. }
  122. cout<<"NO\n";
  123.  
  124.  
  125. }
  126.  
  127. return 0;
  128. }
Success #stdin #stdout 0s 4552KB
stdin
3 57 3 45 -9 45 -9 57
8 50 21 37 8 24 -5 37
stdout
YES