#include #include using namespace std; int n,m,a,b,c,p,q,unapred, resenih; int komande[100005][6]; struct grupa { int x, y, koliko; void init(int _x, int _y, int _koliko) { x = _x; y = _y; koliko = _koliko; } }; grupa vojska[50005], tornjevi[50005]; vector delovi_vojske[2005][2005]; vector delovi_tornjeva[2005][2005]; //map vmx, vmy, tmx, tmy; bool comp(grupa a, grupa b) { return (a.x + a.y) < (b.x + b.y); } float distance(grupa a, grupa b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("war.in","r",stdin); freopen("war.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a>>b>>c; vojska[i].init(a,b,c); delovi_vojske[(int)ceil(a/1000000.0)][(int)ceil(b/1000000.0)].push_back(&vojska[i]); // vmx[a] = vojska[i]; // vmy[b] = vojska[i]; } for(int i=1;i<=m;i++) { cin>>a>>b>>c; tornjevi[i].init(a,b,c); delovi_tornjeva[(int)ceil(a/1000000.0)][(int)ceil(b/1000000.0)].push_back(&tornjevi[i]); // tmx[a] = tornjevi[i]; // tmy[b] = tornjevi[i]; } unapred = 0; resenih = 0; // for(int i=2;i<=n;i++) // { // int najblizi = -1; // float udaljenost = 2e9, u2; // int deox = ceil(vojska[i].x/1000000.0); // int deoy = ceil(vojska[i].y/1000000.0); // for(int j=0;jkoliko == vojska[i].koliko) // { // najblizi = j; // break; // } // // u2 = distance(*delovi_tornjeva[deox][deoy][j], vojska[i]); // if(u2 < udaljenost) // { // udaljenost = u2; // najblizi = j; // } // } // if(najblizi == -1) // continue; // if(delovi_tornjeva[deox][deoy][najblizi]->koliko == vojska[i].koliko) // { // komande[++unapred][1]=vojska[i].x; // komande[unapred][2]=vojska[i].y; // komande[unapred][3]=delovi_tornjeva[deox][deoy][najblizi]->x; // komande[unapred][4]=delovi_tornjeva[deox][deoy][najblizi]->y; // komande[unapred][5]=vojska[i].koliko; // vojska[i].koliko = 0; // delovi_tornjeva[deox][deoy][najblizi]->koliko = 0; // resenih += 2; // } // else if(delovi_tornjeva[deox][deoy][najblizi]->koliko < vojska[i].koliko) // { //// int starix = vojska[i].x, stariy = vojska[i].y; // komande[++unapred][1]=vojska[i].x; // komande[unapred][2]=vojska[i].y; // komande[unapred][3]=delovi_tornjeva[deox][deoy][najblizi]->x; // komande[unapred][4]=delovi_tornjeva[deox][deoy][najblizi]->y; // komande[unapred][5]=delovi_tornjeva[deox][deoy][najblizi]->koliko; // delovi_tornjeva[deox][deoy][najblizi]->koliko = 0; //// komande[unapred][5]=vojska[i].koliko; //// q = vojska[i].koliko; //// p = delovi_tornjeva[deox][deoy][najblizi]->koliko; //// vojska[i].koliko = ceil(sqrt((long long)q*q-(long long)p*p)); //// delovi_tornjeva[deox][deoy][najblizi]->koliko = 0; //// //// komande[++unapred][1]=delovi_tornjeva[deox][deoy][najblizi]->x; //// komande[unapred][2]=delovi_tornjeva[deox][deoy][najblizi]->y; //// komande[unapred][3]=vojska[i].x; //// komande[unapred][4]=vojska[i].y; //// komande[unapred][5]=vojska[i].koliko; // // resenih++; // } //// return 1; // // } unapred = 0; for(int x2=1;x2<=1000;x2++) for(int y2=1;y2<=1000;y2++) { if(delovi_vojske[x2][y2].size() == 0) continue; grupa* izbrani = delovi_vojske[x2][y2][0]; for(int i=1;ix; komande[unapred][2]=delovi_vojske[x2][y2][i]->y; komande[unapred][3]=izbrani->x; komande[unapred][4]=izbrani->y; komande[unapred][5]=delovi_vojske[x2][y2][i]->koliko; izbrani->koliko += delovi_vojske[x2][y2][i]->koliko; delovi_vojske[x2][y2][i]->koliko = 0; } for(int i=0;ikoliko < delovi_tornjeva[x2][y2][i]->koliko) break; komande[++unapred][1]=izbrani->x; komande[unapred][2]=izbrani->y; komande[unapred][3]=delovi_tornjeva[x2][y2][i]->x; komande[unapred][4]=delovi_tornjeva[x2][y2][i]->y; komande[unapred][5]=izbrani->koliko; q = izbrani->koliko; p = delovi_tornjeva[x2][y2][i]->koliko; izbrani->koliko = ceil(sqrt((long long)q*q-(long long)p*p)); delovi_tornjeva[x2][y2][i]->koliko = 0; izbrani->x = delovi_tornjeva[x2][y2][i]->x; izbrani->y = delovi_tornjeva[x2][y2][i]->y; } } for(int i=2;i<=n;i++) { if(vojska[i].koliko == 0) continue; komande[++unapred][1]=vojska[i].x; komande[unapred][2]=vojska[i].y; komande[unapred][3]=vojska[1].x; komande[unapred][4]=vojska[1].y; komande[unapred][5]=vojska[i].koliko; vojska[1].koliko += vojska[i].koliko; } // sort(tornjevi+1,tornjevi+m+1, comp); // cout<<" "<<-1; bool greska = false; for(int i=1;i<=m;i++) { if(tornjevi[i].koliko == 0) continue; // cout<