#include #include #include #include using namespace std; const int maxN = 50000; int n,m; stringstream ss; struct point { unsigned long x, y; int tropers; int distance; }; point troper[maxN]; point tower[maxN]; int indTr[maxN], indTw[maxN]; int GetDistance(int x1, int y1, int x2, int y2) { x1=-x2; y1=-y2; return x1*x1+y1*y1; } void readinput() { for (int i = 0; i < n; i++) { cin>>troper[i].x >>troper[i].y>> troper[i].tropers; // troper[i].distance = GetDistance(troper[i].x, troper[i].y, 0, 0 ); indTr[i] = i; } for (int i = 0; i < m; i++) { cin>>tower[i].x >>tower[i].y>> tower[i].tropers; //tower[i].distance = GetDistance(tower[i].x, tower[i].y, 0, 0 ); indTw[i]=i; } } void QuickSort(point A[], int I[], int lo, int hi) { if (lo < hi) { point pivot = A[I[lo + (hi - lo) / 2]]; int t; int i = lo - 1; int j = hi + 1; while (1) { while (A[I[++i]].tropers > pivot.tropers); while (A[I[--j]].tropers < pivot.tropers); if (i >= j) break; t = I[i]; I[i] = I[j]; I[j] = t; } QuickSort(A, I, lo, j); QuickSort(A, I, j + 1, hi); } } void moveTrops(point& poz1,point& poz2) { ss << poz1.x << " " << poz1.y << " " << poz2.x << " " << poz2.y <<" " << poz1.tropers << "\n"; poz2.tropers+=poz1.tropers; poz1.tropers=0; //ss<< " pos2 tr = " << poz2.tropers << "\n"; } void battle(point& army, point& tower) { //string rez = to_string(army.x) + " " + to_string(army.y) + " " + to_string(tower.x) + " " + to_string(tower.y) + " " + to_string(army.tropers) + "\n"; ss << army.x << " " << army.y << " " << tower.x << " " << tower.y << " " << army.tropers << "\n"; int a = 0; if(army.tropers>tower.tropers) { a = (army.tropers*army.tropers)-(tower.tropers*tower.tropers); if (a!=0) { a = (int)(abs(sqrt(a)) + 0.5); } } army.x = tower.x; army.y = tower.y; tower.tropers=0; army.tropers=a; // ss<< " tr = " << a << "\n"; } void tstPrt() { cout<<"tropers \n"; for (int i = 0; i < n; i++) { cout<< troper[indTr[i]].x << " " << troper[indTr[i]].y << " " << troper[indTr[i]].tropers << "\n"; } cout<<"tower \n"; for (int i = 0; i < m; i++) { cout<< tower[indTw[i]].x << " " << tower[indTw[i]].y << " " << tower[indTw[i]].tropers << "\n"; } } int DumyOne(clock_t begin) { //tstPrt(); QuickSort(troper,indTr,0,n-1); QuickSort(tower,indTw,0,m-1); //tstPrt(); int commandsCo=0; int j=0; for(int i=0; i tower[indTw[j]].tropers) { //batle. Move tropers into tower. //and surveaded move to next troper battle(troper[indTr[i]], tower[indTw[j]]); commandsCo++; if (troper[indTr[i]].tropers>0) { i--; } j++; } else { //get tropers from next pozition int k=i; int z = i; do { k++; if(k0 ) { moveTrops(troper[indTr[i]], troper[indTr[k]]); commandsCo ++; i = k; } else{ break; } } while (troper[indTr[k]].tropers <= tower[indTw[j]].tropers); i=k-1; if(z==i && z+1==n) { if(troper[indTr[i] ].tropers >= tower[indTw[j]].tropers) { battle(troper[indTr[i]], tower[indTw[j]]); commandsCo++; j++; i--; } else { if(j=m) break; } } // if (troper[indTr[n-1]].tropers>0) // { // for (int i = 0; i < m; i++) // { // if (tower[indTw[j]].tropers>0) // { // battle(troper[indTr[n-1]], tower[indTw[i]]); // commandsCo++; // } // } //} cout << commandsCo << "\n" << ss.str(); return 0; } int main() { clock_t begin = clock(); freopen("war.in","r",stdin); freopen("war.out","w",stdout); cin>>n>>m; readinput(); DumyOne(begin); return 0; }