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