I - Turtle Graphics
I번은 실제 대회에 5팀이 푼 문제이지만, 난이도는 높은 편이 아니었습니다.

배치상 뒤에 있었고, 귀찮다는 점에서 건드리지 않은 팀이 많지 않았나 하는 생각입니다.

문제를 간단하게 설명하자면 시작점이 (0, 0)이고 lineto명령어 sequence가 들어올 때 교차하는 점이 발생하지 않게 (cycle이 존재하지 않게) cycle을 제거하고 chain 형태로 계속 그렸을 때의 선분의 수와 길이를 구하는 문제입니다.

모든 명령을 입력받고 그린 다음 최종 그림에 대한 chain을 구하는게 아닌 각 명령이 수행될 때 마다 chain상태를 유지하면서 그리는 것이기 때문에 문제가 쉬워집니다.

주요 알고리즘은 명령이 하나 들어올 때 마다 이전에 chain에 포함된 선분들을 먼저 그려진 순서대로 교차하는지 검사한 후 교차하는 선분 및 이후에 그려진 선분을 chain에서 제거 해버립니다. 그리고 교차점을 구한 후 교차한 선분의 새로운 시작과 끝을 수정하고 chain에 포함시킵니다.

주의할 점은 길이가 0인 선분일 경우 포함 시키지 않는 것과 같은 직선상에 두 선분이 놓여질 경우만 조심하면 됩니다.

상세 구현은 아래에...

~~~ c++
#include

#include

#include

#define X first

#define Y second

#define FROM first

#define TO second

using namespace std;

typedef pair Point;

typedef pair Line;

Line drawLine(Point& from, char dir, int len)

{

Line line(from, from);

switch(dir)

{

case 'E': line.TO.X += len; break;

case 'W': line.TO.X -= len; break;

case 'N': line.TO.Y += len; break;

case 'S': line.TO.Y -= len; break;

}

return line;

}

inline int getLineLength(Line& line)

{ return abs(line.TO.X - line.FROM.X) + abs(line.TO.Y - line.FROM.Y); }
inline bool isVertical(Line& l)

{ return l.FROM.X == l.TO.X; }
inline int ccw(Point& a, Point& b, Point& c)

{ return (a.X*b.Y + b.X*c.Y + c.X*a.Y - a.Y*b.X - b.Y*c.X - c.Y*a.X); }
inline bool inLine(Line& l, Point& p)

{ return (l.FROM.X-p.X)*(l.TO.X-p.X) <= 0 && (l.FROM.Y-p.Y)*(l.TO.Y-p.Y) <= 0; }
bool intersect(Line& l1, Line& l2)

{
int c1, c2, c3, c4;
c1 = ccw(l1.FROM, l1.TO, l2.FROM);
c2 = ccw(l1.FROM, l1.TO, l2.TO);
c3 = ccw(l2.FROM, l2.TO, l1.FROM);
c4 = ccw(l2.FROM, l2.TO, l1.TO);
if(not (c1 | c2 | c3 | c4))
{
if( inLine(l1, l2.FROM) || inLine(l1, l2.TO) ||
inLine(l2, l1.FROM) || inLine(l2, l1.TO))
return true;
else return false;
}
if(c1*c2 <= 0 && c3*c4 <= 0) return true;
return false;

}
void process()

{

string in;

cin >> in;

int n = in.size() / 2;

vector chain;

Point cur(0, 0);

for(int i = 0; i < n; i++)

{

if(in[i*2+1] == '0') continue;

// 입력에 해당하는 선분을 그린다.
Line l = drawLine(cur, in[i*2], in[i*2+1]-'0');

// 지금 선분과 교차하는 선분을 찾는다.
vector::iterator it;

for(it = chain.begin(); it != chain.end() && not intersect(l, *it); it++);

// 교차하는 선분이 있을 경우
if(it != chain.end())

{
Line pl = *it;
// 교차하는 선분부터 이후에 그려진 선분을 다 지운다.
chain.erase(it, chain.end());
// 교차점을 계산한다.
Point pt;
pt.X = isVertical(pl) ? pl.FROM.X : l.TO.X;
pt.Y = isVertical(pl) ? l.TO.Y : pl.FROM.Y;
// 교차점을 기준으로 선분들을 새로 구성한다.
l.FROM = pl.TO = pt;
// 교차한 선분을 chain에 포함시킨다.
if(getLineLength(pl)) chain.push_back(pl);
// 지금 그린 선분을 chain에 포함시킨다. 이때 같은 직선상에 있을 경우는 포함시키지 않는다.
if(isVertical(pl) != isVertical(l))
if(getLineLength(l)) chain.push_back(l);
}

else chain.push_back(l);

// 마지막 점을 갱신한다.
cur = l.TO;

}

int len = 0;

for(int i = 0; i < chain.size(); i++)

len += getLineLength(chain[i]);

cout << chain.size() << " " << len << endl;

}

int main()

{

int t;

cin >> t;

while(t--) process();

}

~~~

• imyoyo님 께서 말씀하신 nlogn 방법 훨씬 직관적이고 좋네요 :)

#include <iostream>   
#include <vector>   
#include <string>   
#include <set>
#include <map>
#define X       first   
#define Y       second   
using namespace std;   
typedef pair<int, int>  Point;   
map<char, Point> move;
void process()   
{   
    string in;   
    cin >> in;   
    int n = in.size() / 2;   
    vector<Point>   chain;   
    set<Point>      visited;
    Point cur(0, 0);   
    chain.push_back(cur);
    visited.insert(cur);
    for(int i = 0; i < n; i++)   
    {   
        int m = in[i*2+1] - '0';
        if(m == '0') continue;
        for(int j = 0; j < m; j++)
        {
            cur.X += move[in[i*2]].X;
            cur.Y += move[in[i*2]].Y;
            if(visited.find(cur) != visited.end())
            {
                for(Point pt = chain.back(); pt != cur; pt = chain.back())
                {
                    visited.erase(pt);
                    chain.pop_back();
                }
            }
            else
            {
                chain.push_back(cur);
                visited.insert(cur);
            }
        }
    }   
    int cnt = 0;
    for(int i = 1; i < chain.size(); i++)   
    {
        if(i == 1) cnt++;
        else if((chain[i-2].X == chain[i-1].X && chain[i-1].X != chain[i].X) ||
                (chain[i-2].Y == chain[i-1].Y && chain[i-1].Y != chain[i].Y) )
            cnt++;
    }
    cout << cnt << " " << chain.size()-1 << endl;   
}   
int main()   
{
    move['E'] = Point( 1,  0);
    move['W'] = Point(-1,  0);
    move['N'] = Point( 0,  1);
    move['S'] = Point( 0, -1);
    int t;   
    cin >> t;   
    while(t--) process();   
}