"#include""\n"#include""\n"#include""\nusing namespace std;\nconst int N=1e3+10;\n\nstruct node\n{\n\tint x, y, w;\n};\n\nint numOfWeights;\ndouble ans, ansX, ansY;\nnode weights[N];\n\n// Read template\ntemplate\ninline void read(T&x)\n{\n\tx=0;\n\tchar s=getchar();\n\tbool f=false;\n\twhile(!(s>='0'&&s<='9'))\n\t{\n\t\tif(s=='-')\n\t\t\tf=true;\n\t\ts=getchar();\n\t}\n\twhile(s>='0'&&s<='9')\n\t{\n\t\tx=(x<<1)+(x<<3)+s-'0';\n\t\ts=getchar();\n\t}\n\tif(f)\n\t\tx=(~x)+1;\n\treturn;\n}\n\n// Calculate potential energy\ndouble calculatePotentialEnergy(double x, double y)\n{\n\tdouble energy=0.0;\n\tfor(int i=1; i<=numOfWeights; i++)\n\t\tenergy+=sqrt((x-weights[i].x)(x-weights[i].x)+(y-weights[i].y)(y-weights[i].y))*weights[i].w;\n\treturn energy;\n}\n\n// Solve using simulated annealing algorithm\nvoid solve()\n{\n\t// Set initial temperature and cooling factor\n\tdouble temperature = 1e5;\n\tdouble coolingFactor = 0.996;\n\t\n\twhile(temperature > 1e-18)\n\t{\n\t\t// Generate a random move\n\t\tdouble tmpX = ansX + (rand() + rand() - RAND_MAX) * temperature;\n\t\tdouble tmpY = ansY + (rand() + rand() - RAND_MAX) * temperature;\n\t\t\n\t\t// Calculate potential energy of the new move\n\t\tdouble tmpEnergy = calculatePotentialEnergy(tmpX, tmpY);\n\t\t\n\t\t// Calculate the difference in energy\n\t\tdouble energyDifference = tmpEnergy - ans;\n\t\t\n\t\t// Accept the move if it improves the solution or with a certain probability\n\t\tif(energyDifference < 0.0 || exp(-energyDifference / temperature) * RAND_MAX > rand())\n\t\t{\n\t\t\tans = tmpEnergy;\n\t\t\tansX = tmpX;\n\t\t\tansY = tmpY;\n\t\t}\n\t\t\n\t\t// Cool down the temperature\n\t\ttemperature *= coolingFactor;\n\t}\n}\n\nint main()\n{\n\tsrand(rand());\n\t\n\t// Read the number of weights and their coordinates and weights\n\tread(numOfWeights);\n\tfor(int i=1; i<=numOfWeights; i++)\n\t{\n\t\tread(weights[i].x);\n\t\tread(weights[i].y);\n\t\tread(weights[i].w);\n\t\tansX += weights[i].x;\n\t\tansY += weights[i].y;\n\t}\n\t\n\t// Calculate the initial average position and potential energy\n\tansX /= numOfWeights;\n\tansY /= numOfWeights;\n\tans = calculatePotentialEnergy(ansX, ansY);\n\t\n\t// Perform the solve function multiple times to improve the solution\n\tfor(int i=1; i<=4; i++)\n\t\tsolve();\n\t\n\t// Print the final average position\n\tprintf("%.3lf %.3lf\n", ansX, ansY);\n\t\n\treturn 0;\n
