남극기지 어렵사와요.

  • fractize
    fractize

    ARCTIC

    예제는 잘 풀리는데
    제출하면 오답으로 나오네요.

    어디서 부터 잘못된 걸까요?

    밑에 소스 첨부합니다.

    #include <iostream>
    #include <list>
    #include <algorithm>
    #include <math.h>
    #include <stdio.h>
    
    using namespace std;
    
    //클래스 전방 선언부
    class Site;
    class Connectioin;
    class Testcase;
    class Community;
    
    void minusSet(list<Site*>&, list<Site*>&);
    float getSiteDist(Site *, Site *);
    float round(float val, int pos) {
        float temp;
        temp = val * pow(10, pos);
        temp = floor(temp + 0.5);
        temp *= pow(10, -pos);
        return temp;
    }
    
    //구조체 선언부
    typedef struct point_t {
        float x;
        float y;
    } PT;
    
    class TestCase {
    private:
        list<Site*> sites;
        void traceSites(Community*, list<Site*>&, Site*);
    
    public:
        void addSite(const PT&);
        void printSites();
        void makeInitialConnection();
        list<Community *> processCommunities();
        void unionCommunities(list<Community*> cons);
    };
    
    class Community {
    private:
        list<Site *> sites;
    
    public:
        float getDist(Community*, Site **, Site **);
        void mergeCommnity(Community*);
        list<Site *> getSites();
    };
    
    //클래스 선언부
    class Connection {
    private:
        Site *endA;
        Site *endB;
        float dist;
    public:
        Connection(Site*, Site*);
        float getDist();
    
        Site* getEndA();
        Site* getEndB();
    
        Site* opposite(Site *);
    
        bool operator==(Connection &);
    };
    
    class Site {
        private:
        PT loc;
        list<Connection*> cons;
    
        public:
        Site(const PT&);
        void setLocation(PT loc);
        PT getLocation();
        list<Site*> getLinkToLst();
        void establishConnectionWithSite(Site *);
        void addConnection(Connection *);
        float getLargestDist();
    
        bool operator==(Site &b);
    };
    
    
    //클래스 멤버함수 구현부
    void TestCase::makeInitialConnection() {
        list<Site*>::iterator startitr = sites.begin();
        list<Site*>::iterator compitr;
        Site *minA;
        Site *minB;
        float minimum;
        if (sites.size() == 0) {
            return;
        }
        list<Site*>::iterator endnoditr = sites.end();
        endnoditr--;
        while (startitr != endnoditr) {
            compitr = startitr;
            compitr++;
            minimum = getSiteDist(*compitr, *startitr);
            minA = *startitr;
            minB = *compitr;
            while (compitr != sites.end()) {
                if (minimum > getSiteDist(*startitr, *compitr)) {
                    minimum = getSiteDist(*startitr, *compitr);
                    minA = *startitr;
                    minB = *compitr;
                }
                compitr++;
            }
            minA->establishConnectionWithSite(minB);
            startitr++;
        }
    }
    
    list<Community*> TestCase::processCommunities() {
        list<Site*> clone(sites.size());
        list<Site*> ss;
        list<Community*> coms;
        copy(sites.begin(), sites.end(), clone.begin());
        while (clone.size() > 0) {
            Community *cPtr = new Community();
            traceSites(cPtr, ss, *clone.begin());
            minusSet(clone, ss);
            ss.clear();
            coms.push_back(cPtr);
        }
        return coms;
    
    }
    
    void minusSet(list<Site*> &a, list<Site*> &b) {
        list<Site*>::iterator bItr = b.begin();
        list<Site*>::iterator fItr;
        while (bItr != b.end()) {
            fItr = find(a.begin(), a.end(), *bItr);
            if (fItr != a.end()) {
                a.erase(fItr);
            }
            bItr++;
        }
    
    }
    
    void TestCase::traceSites(Community* com, list<Site*>& ss, Site* s) {
        ss.push_back(s);
        com->getSites().push_back(s);
        list<Site*> sList = s->getLinkToLst();
        list<Site*>::iterator sItr = sList.begin();
        while (sItr != sList.end()) {
            if (find(ss.begin(), ss.end(), *sItr) == ss.end()) {
                traceSites(com, ss, *sItr);
            } else {
    
            }
            sItr++;
        }
    }
    
    float Site::getLargestDist() {
        float max = 0;
        list<Connection*>::iterator cItr = cons.begin();
        while (cItr != cons.end()) {
            if (max < (*cItr)->getDist()) {
                max = (*cItr)->getDist();
            }
            cItr++;
        }
        return max;
    }
    
    float Community::getDist(Community *con, Site **a, Site **b) {
        float nearst = getSiteDist(*sites.begin(), *con->getSites().begin());
        *a = *sites.begin();
        *b = *con->getSites().begin();
    
        list<Site*>::iterator itra = sites.begin();
        list<Site*>::iterator itrb;
    
        while (itra != sites.end()) {
            itrb = con->getSites().begin();
            while (itrb != con->getSites().end()) {
                if (nearst > getSiteDist(*itra, *itrb)) {
                    nearst = getSiteDist(*itra, *itrb);
                    *a = *itra;
                    *b = *itrb;
                }
                itrb++;
            }
            itra++;
        }
        return nearst;
    
    }
    
    list<Site*> Community::getSites() {
        return sites;
    }
    
    void TestCase::printSites() {
    
        int size = 10;
        list<Community*> clist;
        makeInitialConnection();
    
        while (size > 1) {
            clist = processCommunities();
            unionCommunities(clist);
            size = clist.size();
        }
        float max = 0;
        list<Site*>::iterator sItr = sites.begin();
        while (sItr != sites.end()) {
            if (max < (*sItr)->getLargestDist()) {
                max = (*sItr)->getLargestDist();
            }
            sItr++;
        }
    
        char x[100];
    
        sprintf(x, "%.2f", max);
    
        cout << x << endl;
    
    
        /*
        list<Site*>::iterator itr = sites.begin();
        while (itr != sites.end()) {
            Site *site = *itr;
            cout << "(" << site->getLocation().x << ", " << site->getLocation().y << ")";
            itr++;
        }
        cout << endl;
        */
    }
    
    
    void TestCase::addSite(const PT& pt) {
        Site *site = new Site(pt);
        sites.push_back(site);
    }
    
    Connection::Connection(Site *a, Site *b) : endA(a), endB(b) {
        dist = sqrt((endA->getLocation().x - endB->getLocation().x) * (endA->getLocation().x - endB->getLocation().x)
                     + (endA->getLocation().y - endB->getLocation().y) * (endA->getLocation().y - endB->getLocation().y));
        dist = round(dist, 2);
    }
    
    float Connection::getDist() {
        return dist;
    }
    
    void TestCase::unionCommunities(list<Community*> cons) {
        if (cons.size() == 1) return;
        float nearst = 100000;
        Site* a = 0x00;
        Site* b = 0x00;
        Site* runA = 0x00;
        Site* runB = 0x00;
        list<Community*>::iterator startItr = cons.begin();
        list<Community*>::iterator compItr;
        list<Community*>::iterator endItr = cons.end();
        endItr--;
        while (startItr != endItr) {
            nearst = 100000;
            a = 0x00;
            b = 0x00;
            compItr = startItr;
            compItr++;
            while (compItr != cons.end()) {
                float dist = (*startItr)->getDist(*compItr, &a, &b);
                if (nearst > dist) {
                    nearst = dist;
                    runA = a;
                    runB = b;
                }
    
                compItr++;
            }
            runA->establishConnectionWithSite(runB);
    
            startItr++;
        }
    
    }
    
    bool Connection::operator==(Connection &b) {
        return ((*b.endA == *endA) && (*b.endB == *endB)) || ((*b.endA == *endB) && (*b.endB == *endA));
    }
    
    Site::Site(const PT &pt) {
        loc = pt;
    }
    
    Site* Connection::getEndA() {
        return endA;
    }
    
    Site* Connection::getEndB() {
        return endB;
    }
    
    Site* Connection::opposite(Site *b) {
        Site* ret = 0x00;
        if (*b == *endA) {
            ret = endB;
        } else if (*b == *endB) {
            ret = endA;
        }
        return ret;
    }
    
    
    
    void Site::establishConnectionWithSite(Site *b) {
         Connection *con = new Connection(this, b);
         list<Connection*>::iterator conItr = cons.begin();
         while (conItr != cons.end()) {
             if ((*(*conItr)) == *con) {
                 delete con;
                 return;
             }
             conItr++;
         }
         cons.push_back(con);
         b->addConnection(con);
    }
    
    void Site::addConnection(Connection *con) {
        cons.push_back(con);
    }
    
    list<Site*> Site::getLinkToLst() {
        list<Site*> lst;
        list<Connection*>::iterator itr = cons.begin();
        while (itr != cons.end()) {
            lst.push_back((*itr)->opposite(this));
            itr++;
        }
        return lst;
    }
    
    
    bool Site::operator==(Site &b) {
        return (loc.x == b.loc.x) && (loc.y == b.loc.y);
    }
    
    void Site::setLocation(PT loc) {
        this->loc = loc;
    }
    
    PT Site::getLocation() {
        return this->loc;
    }
    
    float getSiteDist(Site *a, Site *b) {
        return sqrt((a->getLocation().x - b->getLocation().x) * (a->getLocation().x - b->getLocation().x) +
                    (a->getLocation().y - b->getLocation().y) * (a->getLocation().y - b->getLocation().y));
    }
    
    
    int main()
    {
        int testCnt = 0;
        int siteCnt = 0;
        float x = 0;
        float y = 0;
    
        //입력부
        cin >> testCnt;
    
        TestCase tCases[testCnt];
    
        for (int i = 0; i < testCnt; i++) {
            cin >> siteCnt;
            for (int j = 0; j < siteCnt; j++) {
                cin >> x;
                cin >> y;
                PT pt;
                pt.x = x;
                pt.y = y;
                tCases[i].addSite(pt);
            }
         //    tCases[i].printSites();
        }
        //출력부
    
        for (int i = 0; i < testCnt; i++) {
            tCases[i].printSites();
        }
    }
    


    12년 전
3개의 댓글이 있습니다.
  • 장홍준
    장홍준

    저 같은 경우에는 parametric search로 해결했는데
    올려주신 소스가 잘 이해가 안되네요.
    본인의 솔루션을 간략히 올려주시는 게 더 좋을 거 같아요ㅠ


    12년 전 link
  • fractize
    fractize

    우선은 가장 가까운 기지(Site)들끼리 연결(Connection)을 짓습니다.
    그리고 연결된 한 뭉탱이를 Community라고 합니다.
    그리고 각 Community끼리 가장 가까운 Community의 가장 가까운 Site끼리 연결(Connection)합니다.
    이 일을 Community가 단 하나만 남을때 까지 계속 합니다.
    Community가 단 하나만 남으면 모든 Site는 서로 직간접적으로
    연결되어 있다고 간주합니다.
    그럼 모든 Site의 Connection의 길이를 가져와서
    그중에 가장 긴 Connection의 길이를
    답으로 가져오는 것입니다.


    12년 전 link
  • JongMan
    JongMan

    알고리즘은 맞는 것 같은데요. ^^


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.