9개의 댓글이 있습니다.
-
-
legend12 -
소스코드는 여기에~
http://rafb.net/p/XrV6v062.html
17년 전 link
-
-
-
JongMan -
해당 문제 해설과 소스코드는 http://algospot.com/zbxe/openlecture/2567 를 참조하시면 됩니다. ^^
17년 전 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];
vectorp;
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(vectorpoints)
{
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]
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JongMan
오늘의 토론 문제는 오늘 열렸던 SRM373 Hard 인 SpiralConstruction 입니다.
[문제 보기]
토론은 댓글이나 답글로 해주세요~ ^^
17년 전