algospot.com :: 질문과 답변: 남극기지 어렵사와요.

남극기지 어렵사와요.

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

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

밑에 소스 첨부합니다.

#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

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

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

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

12년 전 link

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

12년 전 link

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

12년 전 link

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

SINCE 2007

다가오는 이벤트들

남극기지 어렵사와요.

3개의 댓글이 있습니다.