#include #include > #include #include #include #include struct Vector2{ int x; int y; bool isSet = false; bool isHomoth = false; Vector2(): x(0), y(0) {} Vector2(int x, int y): x(x), y(y) {} Vector2(const Vector2& other) { SetX(other.x); SetY(other.y); } void SetX(int x) { this->x=x; } void SetY(double y) { this->y=y; } void SetSetPoint(bool exp) { this->isSet = exp; } Vector2 Add(const Vector2& other) const { return Vector2(this->x + other.x, this->y + other.y); } Vector2 Substract(const Vector2& other) const { return Vector2(this->x-other.x, this->y-other.y); } double GetDistance(const Vector2& other) const { return std::sqrt((this->x-other.x)*(this->x-other.x) + (this->y-other.y)*(this->y-other.y)); } double GetLength() const { return std::sqrt(x*x + y*y); } int Dot(const Vector2& other) const { return this->x * other.x + this->y * other.y; } double Norm() const { return std::sqrt(x*x+y*y); } Vector2& operator=(const Vector2& rhs) { if(this != &rhs) { this->SetX(rhs.x); this->SetY(rhs.y); } return *this; } Vector2& operator+=(const Vector2& other) { this->x += other.x; this->y += other.y; return *this; } Vector2& operator-=(const Vector2& other) { this->x -= other.x; this->y -= other.y; return *this; } Vector2& operator*=(int other) { this->x*=other; this->y*=other; return *this; } Vector2& operator/=(int other) { this->x/=other; this->y/=other; return *this; } }; Vector2& operator+(Vector2& first, const Vector2& second) { first.Add(second); return first; } Vector2& operator-(Vector2& first, const Vector2& second) { first.Substract(second); return first; } Vector2& operator*(Vector2& first, int multiplier) { first*=multiplier; return first; } double const e = 2.71; int const centerDist = 200; int maxIndex; int dist=0; int cost=0; int missedPoints=0; int const homothetyCost = 2; int const homothetyCostMinus = 6; int const hydraCost = 3; int const stackCost = 15; int N; // number of dots int M; // number of dots in the stack double angle = 0; std::vector coordPoints; std::vector stackPoints; // how to define the lines: 3 functions: one to find the toppest Vector2, leftest/rightest, bottommest check // how to understand when a Vector2 has escaped a field -> check each Vector2 after an operation if it is off lines check // define the angle between the two staight line ->check // decide which thing is more important: dist(between the lines) || cost(cost of the used operations) // for the angle //p1, p2 = x2- x1, y2-y1 // |p1|,|p2|-> take the Vector2s and square(a*a + b*b) //angle = (p1.x*p2.x + p1.y*p2.y) / p1,p2 int findPointIndex(Vector2 a); void findCenter(); bool isPointCentered(Vector2 test); void TrySetPoint(Vector2& a); void Homotethy(Vector2 a, Vector2& b, int k); bool HydraPoint(Vector2 a, Vector2 b); bool TryDrawPoint(Vector2& a); void LinesDist(); void ShortenDist(); int main() { scanf("%d", &N); int x, y; for(int i = 0; i < N; i++) { scanf("%d %d", &x, &y); coordPoints.push_back(Vector2(x, y)); } scanf("%d", &M); for(int i = 0; i < M; i++) { scanf("%d %d", &x, &y); stackPoints.push_back(Vector2(x, y)); } findCenter(); // now iterate through all Vector2s for(int i = 0; i < coordPoints.size(); i++) { if(coordPoints[i].isSet || stackPoints.size() == 0) continue; TrySetPoint(coordPoints[i]); } for(int i = 0; i < coordPoints.size(); i++) { if(!coordPoints[i].isSet) missedPoints++; } LinesDist(); // calculate the result double result = 25*((double)dist+0.01*(std::pow(e/2, missedPoints))*((double)dist+1))+cost*(((double)dist+1)/50); std::cout<= coordPoints[maxIndex].x-centerDist && test.y <= coordPoints[maxIndex].y+centerDist && test.y >= coordPoints[maxIndex].y-centerDist) return true; return false; } int CenterPoints(Vector2 a) // find all center Vector2s { int centerCount = 0; for(int i = 0; i < coordPoints.size(); i++) { if(coordPoints[i].x <= a.x+centerDist && coordPoints[i].x >= a.x-centerDist && coordPoints[i].y <= a.y+centerDist && coordPoints[i].y >= a.y-centerDist) centerCount++; } return centerCount; } void findCenter() // find the max center and set Vector2s in the center as set { int max = 0; for(int i = 0; i < coordPoints.size(); i++) { int currentCenter = CenterPoints(coordPoints[i])-1; if(currentCenter > max) { max = currentCenter; maxIndex=i; } } // set the Vector2s in the vector as set for(int i = 0; i < coordPoints.size(); i++) { if(coordPoints[i].x <= coordPoints[maxIndex].x+centerDist && coordPoints[i].x >= coordPoints[maxIndex].x-centerDist && coordPoints[i].y <= coordPoints[maxIndex].y+centerDist && coordPoints[i].y >= coordPoints[maxIndex].y-centerDist) coordPoints[i].isSet=true; } } void TrySetPoint(Vector2& point) { Vector2 a = coordPoints[0]; for(int j = 0; j < coordPoints.size(); j++) { a = coordPoints[j]; Vector2 test1=point-a; test1=test1*2 +a; Vector2 test2=point-a; test2=test2*(-2)+a; if(isPointCentered(test1)) { Homotethy(coordPoints[j],point,2); } else if(isPointCentered(test2)) { Homotethy(coordPoints[j],point,-2); } else if(!HydraPoint(test1, point)) { Homotethy(coordPoints[j],point,2); } else if(!HydraPoint(test2, point)) { Homotethy(coordPoints[j],point,-2); HydraPoint(coordPoints[j], point); } else { // evaluate it to the max TryDrawPoint(point); } } } void Homotethy(Vector2 a, Vector2& b, int k) { // initialize the vector Vector2 test; test= b-a; test*=k; test+=a; if(isPointCentered(test)) { // increase the cost summ if(k == 2) cost+=homothetyCost; else cost+=homothetyCostMinus; b.isSet=true; printf("1 %d %d %d %d %d \n", k, a.x, a.y,b.x, b.y); b= test; } } bool HydraPoint(Vector2 a, Vector2 b)// { Vector2 b1; Vector2 b2; b1=(a-b)*2 + a; b2=(a-b)*2 + a; if(b1.x < 0 || b1.x > 1000 || b1.y < 0 || b1.y > 1000 || !isPointCentered(b1) || !isPointCentered(b2)) return true; int bIndex= findPointIndex(b); coordPoints.erase(coordPoints.begin()+bIndex); b1.isSet=true; b2.isSet=true; coordPoints.push_back(b1); coordPoints.push_back(b2); printf("2 %d %d %d %d \n", a.x, a.y, b.x, b.y); //increase the cost sum cost+=hydraCost; return false; } bool TryDrawPoint(Vector2& a) { if(stackPoints.size() == 0) return false; a = stackPoints.back(); stackPoints.pop_back(); if(isPointCentered(a)) { printf("3 %d %d \n", a.x, a.y); cost+=stackCost; a.isSet=true; return true; } printf("3 %d %d \n", a.x, a.y); return false; } int FindMaxYIndex() { int y = coordPoints[0].y; int maxIndex = 0; int i; for(i = 0; i < coordPoints.size(); i++) { if(coordPoints[i].y > y) { y = coordPoints[i].y; maxIndex=i; } } return i; } void LinesDist() { Vector2 xMax = coordPoints[0]; Vector2 xMin = coordPoints[0]; Vector2 yMax = coordPoints[0]; Vector2 yMin = coordPoints[0]; for(int i =0 ; i xMax.x) xMax = coordPoints[i]; if(coordPoints[i].x < xMin.x) xMin = coordPoints[i]; if(coordPoints[i].y > yMax.y) yMax = coordPoints[i]; if(coordPoints[i].y < yMin.y) yMin = coordPoints[i]; } int xDist = xMax.x - xMin.x; int yDist = yMax.y - yMin.y; double angle; if(xDist < yDist) { dist=xDist; TrySetPoint(xMax); angle=std::acos(xMax.Dot(xMin)/(xMax.Norm()*xMin.Norm())); } else { TrySetPoint(yMax); dist=yDist; angle=std::acos(yMax.Dot(yMin)/(yMax.Norm()*yMin.Norm())); } }