## 남극기지 어렵사와요.

• 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 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();
void establishConnectionWithSite(Site *);
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*>::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;
*/
}

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

cons.push_back(con);
}

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].printSites();
}
//출력부

for (int i = 0; i < testCnt; i++) {
tCases[i].printSites();
}
}


11년 전
##### 3개의 댓글이 있습니다.

• 장홍준

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

11년 전

• fractize

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

11년 전

• JongMan

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

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