#include #include #include #include #include #include #include using namespace std; const double TIME_LIMIT = 4.7; const double PI = acos(-1); const double eps = 0.0001; double startTime; mt19937 rnd(69420); struct point { double x, y; int ind; point(){} point(double x, double y) { this->x = x; this->y = y; } point(double x, double y, int ind) { this->x = x; this->y = y; this->ind = ind; } point operator +(point other) { point output = *this; output.x += other.x; output.y += other.y; return output; } void operator +=(point other) { this->x += other.x; this->y += other.y; } bool operator ==(point other) { if(this->x==other.x && this->y==other.y) return true; return false; } void applyChange(double angle, double xDelta, double yDelta) { angle = angle/180*PI; this->x += xDelta; this->y += yDelta; //double xPrime = this->x*cos(angle) - this->y*sin(angle); //double yPrime = this->x*sin(angle) + this->y*cos(angle); //this->x = xPrime; //this->y = yPrime; } }; double getDist(point A, point B) { return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y)); } double calcSurface(point A, point B, point C) { return((A.x*B.y + A.y*C.x + B.x*C.y) - (A.y*B.x + A.x*C.y + B.y*C.x))/2.0; } point pivotPoint; bool cmpPoint(const point A, const point B) { if(calcSurface(pivotPoint, A, B)>0) return true; return false; } double sign(double x) { if(x<-eps) return -1; if(abs(x)eps) return 1; } bool areCrossing(point A1, point A2, point B1, point B2) { /* if(abs(calcSurface(B1, A1, B2))=min(B1.x, B2.x) && A1.x<=max(B1.x, B2.x)) return true; if(abs(calcSurface(B1, A2, B2))=min(B1.x, B2.x) && A2.x<=max(B1.x, B2.x)) return true; if(abs(calcSurface(A1, B1, A2))=min(A1.x, A2.x) && B1.x<=max(A1.x, A2.x)) return true; if(abs(calcSurface(A1, B2, A2))=min(A1.x, A2.x) && B2.x<=max(A1.x, A2.x)) return true; */ //cout << calcSurface(A1, B1, A2) << " != " << calcSurface(A1, B2, A2) << '\n'; if(sign(calcSurface(A1, B1, A2))!=sign(calcSurface(A1, B2, A2)) && sign(calcSurface(B1, A1, B2))!=sign(calcSurface(B1, A2, B2))) return true; return false; } struct polygon { vector v; polygon(){} polygon(vector v) { this->v = v; } double surface() { double S = 0; for(int i = 1;iv) { curr.applyChange(angle, xDelta, yDelta); } } }; struct figure { int index; point centroid; vector v; vector allPoints; figure(){} figure(vector v, vector allPoints) { this->v = v; this->allPoints = allPoints; centroid.x = 0; centroid.y = 0; for(point p: allPoints) { centroid += p; } centroid.x /= allPoints.size(); centroid.y /= allPoints.size(); } void updateCentroid() { centroid.x = 0; centroid.y = 0; for(point p: allPoints) { centroid += p; } centroid.x /= allPoints.size(); centroid.y /= allPoints.size(); } void applyChange(double angle, double xDelta, double yDelta) { for(polygon &curr: this->v) { curr.applyChange(angle, xDelta, yDelta); } for(point &curr: this->allPoints) { curr.applyChange(angle, xDelta, yDelta); } this->centroid.applyChange(angle, xDelta, yDelta); } }; bool areIntersectng(polygon A, polygon B) { if(B.isInside(A.v[0])==true) { //if((clock()-startTime)/CLOCKS_PER_SEC>TIME_LIMIT) return false; return true; } if(A.isInside(B.v[0])==true) { //if((clock()-startTime)/CLOCKS_PER_SEC>TIME_LIMIT) return false; return true; } for(int p1 = 0;p1TIME_LIMIT) return false; for(int p2 = 0;p2 allPoints; vector
v = figures; for(int i = 0;ia[i].angle, this->a[i].x, this->a[i].y); } for(int f = 0;fa[f].used==false) { mul *= 1.5; for(int i = 0;i &v) { point centroid = point(0, 0); for(point p: v) { centroid.x += p.x; centroid.y += p.y; } centroid.x /= v.size(); centroid.y /= v.size(); return centroid; } bool forbidden[505]; vector layer[505]; solution solve(vector
fig, long long scale) { int startIndex = 505; solution currSolution = solution(); for(figure curr: fig) { //cout << p.ind << " = true" << '\n'; currSolution.a[curr.index].used = true; } vector all; for(int i = 0;i xPos; for(int i = 0;i=0;j--) { if(areIntersectng(fig[i], fig[j])==true) { fail = true; break; } if((clock()-startTime)/CLOCKS_PER_SEC>TIME_LIMIT) break; } if(fail==false) r = mid; else l = mid + 1; fig[i].applyChange(0, 0, -mid); } currSolution.a[fig[i].index].y += r + 1; fig[i].applyChange(0, 0, r + 1); lastY += r + 1; } return currSolution; } int main() { ifstream cin("packing.in"); ofstream fout("packing.out"); //solve(vector {point(9, 5), point(9, 4), point(10, 6), point(12, 3), point(9, 2), point(7, 4), point(7, 6)}); //return 0; int F; cin >> F; for(int i = 0;i p; figures.push_back(figure()); cin >> P; for(int j = 0;j> x >> y; p.push_back(point(x, y)); figures[i].allPoints.push_back(point(x, y)); } int M; cin >> M; for(int j = 0;j> K; vector v; for(int t = 0;t> ind; v.push_back(p[ind]); } figures[i].v.push_back(polygon(v)); } figures[i].index = i; figures[i].updateCentroid(); } startTime = clock(); srand(time(0)); solution answer = solution(); for(int percent = 100;percent>=100;percent/=2) { if((clock()-startTime)/CLOCKS_PER_SEC>TIME_LIMIT) break; vector
v; for(int i = 0;i currSolution.evaluate(F)) { cout << percent << "^^^^\n"; answer = currSolution; } } //cout << answer.a[0].used << answer.a[1].used << '\n'; //cout << answer.isCorrect(F) << '\n'; //cout << "score: " << answer.evaluate(F) << "\n"; for(int i = 0;i{point(0, 1), point(0, 0), point(1, 0), point(1, 1)}); //cout << P.isInside(point(0.5, 5.5)) << '\n'; } /* 3 4 6 4 6 3 7 3 7 4 1 4 0 1 2 3 4 3 3 3 2 4 2 4 3 1 4 0 1 2 3 4 10 7 10 6 11 6 11 7 1 4 0 1 2 3 */