algospot.com :: 과거 게시판: [editorial] 오늘의 하드풀기: SRM373 Div 1 Hard, SpiralConstruction

[editorial] 오늘의 하드풀기: SRM373 Div 1 Hard, SpiralConstruction

JongMan

오늘의 토론 문제는 오늘 열렸던 SRM373 Hard 인 SpiralConstruction 입니다.
[문제 보기]
토론은 댓글이나 답글로 해주세요~ ^^

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

16년 전

9개의 댓글이 있습니다.

JongMan

크와아앙 풀었따;;; 아 이렇게 어렵게 풀다니 엉엉 ㅠㅠ

16년 전 link
legend12

풀었음~ 다소 간단하게 푼것 같긴 한데.. CCW 에서 오버플로우 나는것 때문에 삽질을 -_-;;;

16년 전 link
legend12

소스코드는 여기에~
http://rafb.net/p/XrV6v062.html

16년 전 link
JongMan

소스코드는 댓글에 인용에 접기 옵션 써서 올려주세요~ rafb 는 하루 지나면 지워져요~
근데 그분은 백트로 푸셨군 ㅎㄷㄷ 저는 dp라능.. 내일 소스코드 올리겠다능..

16년 전 link
astein

에디토리얼에 (소스코드 포함) 올렸다는 [...]

16년 전 link
legend12

댓글에 접기 인용이 가능하다는걸 몰랐군 ㅎㄷㄷ
[spoiler="소스코드"][code c++]#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
//#define abs(a) (a < 0 ? -(a) : a)
#define sqr(a) ((a) * (a))
#define eps 1.0e-9
#define pi (2.0 * acos(0.0))
#define sz(a) ((int)a.size())
#define clr(a, b) (memset(a, b, sizeof(a)))
//#define pb push_back
#define MAKEONE(a) ((a) == 0 ? a : (a) / abs(a))
using namespace std;
typedef long long ll;
typedef vector VI;
typedef vector VS;
typedef vector VD;
typedef set SI;
struct point {
int x, y;
};
struct line {
point pa, pb;
};
int ccw(point pa, point pb, point pc) {

return MAKEONE((pa.x - pb.x) * (pb.y - pc.y) - (pb.x - pc.x) * (pa.y - pb.y));
}

bool InLine(line l, point p) {

if (min(l.pa.x, l.pb.x) <= p.x && p.x <= max(l.pa.x, l.pb.x) && min(l.pa.y, l.pb.y) <= p.y && p.y <= max(l.pa.y, l.pb.y))

return true;
return false;

}

bool Intersect(line la, line lb) {

int c1 = ccw(la.pa, la.pb, lb.pa), c2 = ccw(la.pa, la.pb, lb.pb);

int c3 = ccw(lb.pa, lb.pb, la.pa), c4 = ccw(lb.pa, lb.pb, la.pb);

if (c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) {

if (InLine(la, lb.pa) || InLine(la, lb.pb) || InLine(lb, la.pa) || InLine(lb, la.pb)) return true;
return false;
}
if (c1 * c2 <= 0 && c3 * c4 <= 0) return true;

return false;

}
class SpiralConstruction {
public:
vector v;
point vp[20];
point p;
int use[20];
line l1, l2;
int maxv;
void longest(int idx) {
int i, j;
int dx, dy;
if (idx == sz(v)) return ;
for(i = 0; i < sz(v); i++) {
if (use[i] == 1) continue;
if (ccw(vp[idx-1], vp[idx], v[i]) < 0) continue;
l1.pa = vp[idx]; l1.pb = vp[idx];
dx = v[i].x - vp[idx].x;
dy = v[i].y - vp[idx].y;
while(1) {
l1.pb.x += dx; l1.pb.y += dy;
if (l1.pb.x < -1000 || l1.pb.x > 1000 || l1.pb.y < -1000 || l1.pb.y > 1000) break;
}
if (ccw(vp[idx-1], vp[idx], v[i]) == 0 && InLine(l1, vp[idx-1])) continue;
for(j = 1; j < idx; j++) {
l2.pa = vp[j-1]; l2.pb = vp[j];
if (Intersect(l1, l2)) break;
}
if (j != idx) continue;
use[i] = 1;
maxv = max(maxv, idx + 1);
vp[idx+1] = v[i];
longest(idx + 1);
use[i] = 0;
}
}
int longestSpiral(VS points) {
int i;
v.clear();
for(i = 0; i < sz(points); i++) {
sscanf(points[i].c_str(), "%d %d", &p.x, &p.y);
v.push_back(p);
use[i] = 0;
}
vp[0].x = 0; vp[0].y = 0;
maxv = 1;
for(i = 0; i < sz(v); i++) {
use[i] = 1;
vp[1] = v[i];
longest(1);
use[i] = 0;
}
return maxv;
}
};[/code]
[/spoiler]

16년 전 link
JongMan

근데 너는 algorithm 도 인클루드했으면서 왜 max min 매크로가 있는거냐 -_-;;

16년 전 link
JongMan

해당 문제 해설과 소스코드는 http://algospot.com/zbxe/openlecture/2567 를 참조하시면 됩니다. ^^

16년 전 link
JongMan
다음은 제 소스코드입니다.
[spoiler="열어보기"]~~~ cpp
#include
#include
#include
#include
#include
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef long long ll;
int cache[1<<15][16][16];
struct point
{
int y, x;
point(){}
point(int y, int x) : y(y), x(x) {}
};
struct SpiralConstruction
{
int n;
int left[16][16], right[16][16];
vector p;
inline int ccw(const point& a, const point& b, const point& c)
{
int x1 = b.x - a.x, y1 = b.y - a.y;
int x2 = c.x - a.x, y2 = c.y - a.y;
return x1*y2 - y1*x2;
}
int sgn(int x) { return x < 0 ? -1 : (x > 0 ? 1 : 0); }
bool isValid(int set, int a, int b)
{
set &= ~(1< set &= ~(1< if((left[a][b]&set) && (right[a][b]&set)) return false;
int zero = set&~(left[a][b]|right[a][b]);
int ys = sgn(p[b].y - p[a].y), xs = sgn(p[b].x - p[a].x);
REP(i,n) if((zero&(1< return true;
}
int go(int points, int a, int b)
{
int& ret = cache[points>>1][a][b]; if(ret != -1) return ret;
ret = 0;
REP(c,n) if((points&(1<= 0) if(isValid(points, b, c))
ret >?= go(points | (1< return ret;
}
int longestSpiral(vector points)
{
n = points.sz;
if(n <= 2) return n;
p.pb(point(0,0));
REP(i,n) { int y, x; sscanf(points[i].c_str(), "%d %d", &x, &y); p.pb(point(y, x)); }

n = p.sz;
CLEAR(cache,-1);
REP(i,n) REP(j,n) if(i != j)
{
left[i][j] = right[i][j] = 0;
REP(k,n)
{
int x = ccw(p[i], p[j], p[k]);
if(x > 0) left[i][j] |= (1< if(x < 0) right[i][j] |= (1< }
}
int ret = 0;
FOR(i,1,n)
ret >?= go(1+(1<<i), 0, i) + 1;
return ret;
}
};
```
Astein 이 올린 에디토리얼과 비슷한 DP 솔루션이고요. ^^ 특이할 만한 것은 left[i][j] 와 right[i][j] 에 i 에서 시작해서 j 를 통과하는 반직선을 기준으로 왼쪽에 있는 점들과 오른쪽에 있는 점들의 비트마스크를 미리 저장해서, 좀 더 validity 를 빠르게 계산하려고 한 것 정도가 되겠네요.
사실 이것도 느릴 것 같아서 ㅎㄷㄷ 했는데 위에 보니 legend12s 는 백트래킹으로 풀었더라는.. ㅎㄷㄷ[/spoiler]
```
16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] 오늘의 하드풀기: SRM373 Div 1 Hard, SpiralConstruction

9개의 댓글이 있습니다.