Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int N = 100005;
- struct point{
- double x,y;
- bool operator<(point&b){return y<b.y || y==b.y && x<b.x;}
- };
- int n,m,d;
- int i,j,k;
- point p1[N], p2[N], s[N*2];
- bool u1[N], u2[N];
- void add(point&b, point&a){
- s[d].x = s[d-1].x+(a.x-b.x);
- s[d].y = s[d-1].y+(a.y-b.y);
- ++d;
- }
- int main(){
- cin>>n>>m;
- for(i=0;i<n;++i) cin>>p1[i].x>>p1[i].y;
- for(i=0;i<m;++i) cin>>p2[i].x>>p2[i].y;
- p1[n]=p1[0];
- p2[m]=p2[0];
- for(i=k=0;k<n;++k) if(p1[k]<p1[i]) i=k;
- for(j=k=0;k<m;++k) if(p2[k]<p2[j]) j=k;
- d=1;
- s[0].x = p1[i].x+p2[j].x;
- s[0].y = p1[i].y+p2[j].y;
- for(;;){
- if(i==n) i=0;
- if(j==m) j=0;
- if(u1[i] && u2[j]) break;
- 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){
- add(p2[j], p2[j+1]);
- u2[j]=true;
- ++j;
- }else{
- add(p1[i], p1[i+1]);
- u1[i]=true;
- ++i;
- }
- }
- for(i=0;i<d-1;++i){
- cout<<s[i].x<<' '<<s[i].y<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment