http://acm.pku.edu.cn/JudgeOnline/problem?id=1133
Код:
#include <cstdio> #include <cstring> #include <cstdlib> #include <climits> using namespace std; const int MAX_STAR = 1000; const int MAX_STAR_PER_CONSTEL = 500; const int NAME_LEN = 50; const int COOR_BOUND = 100; const int MAX_OCCUR = 500000; struct Star { int x; int y; int bright; }; int starCmp (const void* star1, const void* star2) { int result = ((Star*)star1)->x - ((Star*)star2)->x; if (result == 0) { result = ((Star*)star1)->y - ((Star*)star2)->y; } return result; } class Constel { private: char m_name[NAME_LEN]; Star m_star[MAX_STAR_PER_CONSTEL]; int m_starCount; public: void init() { m_starCount = 0; } void addStar(Star star) { m_star[m_starCount] = star; m_starCount++; } int bright() { int result = 0; for (int i = 0; i < m_starCount; i++) { result += m_star[i].bright; } return result; } void input() { scanf("%d %s", &m_starCount, m_name); for (int i = 0; i < m_starCount; i++) { scanf("%d %d", &m_star[i].x, &m_star[i].y); } } char* name() { return m_name; } void printConstel() { for (int i = 0; i < m_starCount; i++) { printf("(%d,%d)", m_star[i].x, m_star[i].y); if (i < m_starCount - 1) { printf(" "); } else { printf("\n"); } } } Star star(int i) { return m_star[i]; } int starCount() { return m_starCount; } void sortStar() { qsort(m_star, m_starCount, sizeof(Star), starCmp); } }; bool m_haveStar[COOR_BOUND * 2 + 1][COOR_BOUND * 2 + 1]; int m_starNo[COOR_BOUND * 2 + 1][COOR_BOUND * 2 + 1]; class Map { private: Star m_star[MAX_STAR]; int m_starCount; inline int coorMap(int coor) { return coor + COOR_BOUND; } public: bool input() { bool haveNext = false; scanf("%d", &m_starCount); if (m_starCount > 0) { haveNext = true; memset(m_haveStar, 0, sizeof(m_haveStar)); for (int i = 0; i < m_starCount; i++) { scanf("%d %d %d", &m_star[i].x, &m_star[i].y, &m_star[i].bright); m_haveStar[coorMap(m_star[i].x)][coorMap(m_star[i].y)] = true; m_starNo[coorMap(m_star[i].x)][coorMap(m_star[i].y)] = i; } } return haveNext; } bool haveStar(int x, int y) { bool have; if (x > COOR_BOUND || x < -COOR_BOUND || y > COOR_BOUND || y < -COOR_BOUND ) { have = false; } else { have = m_haveStar[coorMap(x)][coorMap(y)]; } return have; } Star star(int i) { return m_star[i]; } Star star(int x, int y) { return m_star[m_starNo[coorMap(x)][coorMap(y)]]; } int starCount() { return m_starCount; } }; struct Occur{ Star leftLow; Star lowRight; Star rightHigh; Star highLeft; }; int occurCmp(const void* occur1, const void* occur2) { Occur* p1 = (Occur*)occur1; Occur* p2 = (Occur*)occur2; int result = starCmp(&p1->leftLow, &p2->leftLow); if (result == 0) { result = starCmp(&p1->lowRight, &p2->lowRight); } if (result == 0) { result = starCmp(&p1->rightHigh, &p2->rightHigh); } if (result == 0) { result = starCmp(&p1->highLeft, &p2->highLeft); } return result; } Occur m_occur[MAX_OCCUR]; class Solution { private: Map m_map; int m_sketchCount; Constel m_sketch; int m_occurCount; Constel m_brightest; Constel checkOccur(Star occurStar1, Star occurStar2) { int sinUp; int cosUp; int down; getAngle(m_sketch.star(0), m_sketch.star(1), occurStar1, occurStar2 , sinUp, cosUp, down ); Constel occurConstel; occurConstel.init(); occurConstel.addStar(occurStar1); occurConstel.addStar(occurStar2); for (int i = 2; i < m_sketch.starCount(); i++) { Star oldStar = m_sketch.star(i); oldStar.x = occurStar1.x + (oldStar.x - m_sketch.star(0).x); oldStar.y = occurStar1.y + (oldStar.y - m_sketch.star(0).y); Star newStar = rotate(occurStar1, oldStar, sinUp, cosUp, down); if (m_map.haveStar(newStar.x, newStar.y)) { newStar.bright = m_map.star(newStar.x, newStar.y).bright; occurConstel.addStar(newStar); } else { occurConstel.init(); break; } } return occurConstel; } void dealWithOneStar() { m_occurCount = m_map.starCount(); Star brightest; brightest = m_map.star(0); for (int i = 1; i < m_occurCount; i++) { if (m_map.star(i).bright > brightest.bright) { brightest = m_map.star(i); } } m_brightest.init(); m_brightest.addStar(brightest); } inline void getAngle(Star sketchStar1, Star sketchStar2 , Star occurStar1, Star occurStar2 , int& sinUp, int& cosUp, int& down ) { int oldX = sketchStar2.x - sketchStar1.x; int oldY = sketchStar2.y - sketchStar1.y; int newX = occurStar2.x - occurStar1.x; int newY = occurStar2.y - occurStar1.y; sinUp = oldX * newY - newX * oldY; cosUp = oldX * newX + oldY * newY; down = oldX * oldX + oldY * oldY; } void removeRepeat() { qsort(m_occur, m_occurCount, sizeof(Occur), occurCmp); int oldOccurCount = m_occurCount; int i = 0; while (i < oldOccurCount - 1) { int j = i + 1; while (j < oldOccurCount && occurCmp(&m_occur[i], &m_occur[j]) == 0) { //printf("%d %d\n", i, j); m_occurCount--; j++; } i = j; } } inline Star rotate(Star center, Star old, int sinUp, int cosUp, int down) { Star result; int relativeX = old.x - center.x; int relativeY = old.y - center.y; int xUp = relativeX * cosUp - relativeY * sinUp; int yUp = relativeX * sinUp + relativeY * cosUp; if (xUp % down == 0 && yUp % down == 0) { result.x = center.x + xUp / down; result.y = center.y + yUp / down; } else { result.x = COOR_BOUND + 1; result.y = COOR_BOUND + 1; } return result; } inline int starDis(Star star1, Star star2) { return (star1.x - star2.x) * (star1.x - star2.x) + (star1.y - star2.y) * (star1.y - star2.y); } void toOccur(Constel& constel, Occur& occur) { occur.leftLow = constel.star(0); occur.lowRight= constel.star(0); occur.rightHigh= constel.star(0); occur.highLeft = constel.star(0); for (int i = 1; i < constel.starCount(); i++) { Star current = constel.star(i); if(current.x < occur.leftLow.x || current.x == occur.leftLow.x && current.y < occur.leftLow.y ) { occur.leftLow = current; } if(current.y < occur.lowRight.y || current.y == occur.lowRight.y && current.x > occur.lowRight.x ) { occur.lowRight = current; } if(current.x > occur.rightHigh.x || current.x == occur.rightHigh.x && current.y > occur.rightHigh.y ) { occur.rightHigh = current; } if(current.y > occur.highLeft.y || current.y == occur.highLeft.y && current.x < occur.highLeft.x ) { occur.highLeft = current; } } } public: bool input() { bool haveNext = m_map.input(); if(haveNext) { scanf("%d", &m_sketchCount); } return haveNext; } bool inputConstel() { bool haveNext = false; if (m_sketchCount > 0) { haveNext = true; m_sketch.input(); m_sketchCount--; } return haveNext; } void solve() { if (m_sketch.starCount() == 1) { dealWithOneStar(); } else if (m_sketch.starCount() > m_map.starCount()) { m_occurCount = 0; } else { m_occurCount = 0; int maxBright = INT_MIN; for (int i = 0; i < m_map.starCount(); i++) { Star occurStar1 = m_map.star(i); for (int j = 0; j < m_map.starCount(); j++) { if (j != i) { Star occurStar2 = m_map.star(j); Constel occurConstel = checkOccur(occurStar1, occurStar2); if (occurConstel.starCount() > 0) { occurConstel.sortStar(); int bright = occurConstel.bright(); if(bright > maxBright) { maxBright = bright; m_brightest = occurConstel; } toOccur(occurConstel, m_occur[m_occurCount]); m_occurCount++; } } } } removeRepeat(); } } void output() { printf("%s occurs %d time(s) in the map.\n", m_sketch.name(), m_occurCount); if (m_occurCount > 0) { printf("Brightest occurrence: "); m_brightest.printConstel(); } } }; int main() { Solution solution; int mapCount = 1; while (solution.input()) { printf("Map #%d\n", mapCount); while (solution.inputConstel()) { solution.solve(); printf("\n"); solution.output(); } printf("-----\n"); mapCount++; } return 0; }