Al3XS0n

Untitled

Nov 21st, 2020
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int N = 100005;
  5.  
  6. struct point{
  7. double x,y;
  8. bool operator<(point&b){return y<b.y || y==b.y && x<b.x;}
  9. };
  10.  
  11. int n,m,d;
  12. int i,j,k;
  13. point p1[N], p2[N], s[N*2];
  14. bool u1[N], u2[N];
  15.  
  16. void add(point&b, point&a){
  17. s[d].x = s[d-1].x+(a.x-b.x);
  18. s[d].y = s[d-1].y+(a.y-b.y);
  19. ++d;
  20. }
  21.  
  22. int main(){
  23.  
  24. cin>>n>>m;
  25. for(i=0;i<n;++i) cin>>p1[i].x>>p1[i].y;
  26. for(i=0;i<m;++i) cin>>p2[i].x>>p2[i].y;
  27.  
  28. p1[n]=p1[0];
  29. p2[m]=p2[0];
  30.  
  31. for(i=k=0;k<n;++k) if(p1[k]<p1[i]) i=k;
  32. for(j=k=0;k<m;++k) if(p2[k]<p2[j]) j=k;
  33.  
  34. d=1;
  35. s[0].x = p1[i].x+p2[j].x;
  36. s[0].y = p1[i].y+p2[j].y;
  37.  
  38.  
  39. for(;;){
  40. if(i==n) i=0;
  41. if(j==m) j=0;
  42. if(u1[i] && u2[j]) break;
  43.  
  44. if(u1[i] || !u2[j] && (p1[i+1].x-p1[i].x)*(p2[j+1].y-p2[j].y)-(p1[i+1].y-p1[i].y)*(p2[j+1].x-p2[j].x)<0){
  45. add(p2[j], p2[j+1]);
  46. u2[j]=true;
  47. ++j;
  48. }else{
  49. add(p1[i], p1[i+1]);
  50. u1[i]=true;
  51. ++i;
  52. }
  53. }
  54.  
  55.  
  56. for(i=0;i<d-1;++i){
  57. cout<<s[i].x<<' '<<s[i].y<<endl;
  58. }
  59.  
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment