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;
}