結果
問題 | No.2180 Comprehensive Line Segments |
ユーザー | lddlinan |
提出日時 | 2023-03-17 02:38:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,905 bytes |
コンパイル時間 | 1,069 ms |
コンパイル使用メモリ | 104,812 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 09:49:24 |
合計ジャッジ時間 | 2,180 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 31 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 5 ms
6,940 KB |
testcase_10 | AC | 12 ms
6,944 KB |
testcase_11 | AC | 23 ms
6,944 KB |
testcase_12 | AC | 11 ms
6,940 KB |
testcase_13 | AC | 32 ms
6,944 KB |
testcase_14 | AC | 24 ms
6,940 KB |
testcase_15 | AC | 29 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,944 KB |
testcase_17 | AC | 5 ms
6,940 KB |
testcase_18 | AC | 33 ms
6,944 KB |
testcase_19 | AC | 14 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,940 KB |
testcase_21 | AC | 6 ms
6,940 KB |
testcase_22 | AC | 2 ms
6,944 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 4 ms
6,940 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 5 ms
6,940 KB |
ソースコード
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <math.h> #include <map> #include <vector> #include <queue> #include <deque> #include <set> #include <stack> #include <algorithm> #include <array> #include <unordered_set> #include <unordered_map> #include <string> using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; typedef struct { int x, y; } Point; char inseg(Point a, Point b, Point c) { LL dx1=a.x-b.x; LL dy1=a.y-b.y; LL dx2=c.x-b.x; LL dy2=c.y-b.y; LL dd = dx1*dy2-dy1*dx2; if (dd) return 0; if ((c.x-a.x)*(c.x-b.x)<=0&&(c.y-a.y)*(c.y-b.y)<=0) return 1; return 0; } char cross(Point a, Point b, Point c, Point d) { LL dx1=a.x-b.x; LL dy1=a.y-b.y; LL dx2=c.x-b.x; LL dy2=c.y-b.y; LL dd = dx1*dy2-dy1*dx2; if (dd==0) { if ((c.x-a.x)*(b.x-a.x)>=0 && (c.y-a.y)*(b.y-a.y)>=0) return 1; // no care for reverse return 0; } LL dx=d.x-c.x; LL dy=d.y-c.y; // (c.y+k*dy-b.y)*(a.x-b.x) = (a.y-b.y)*(c.x+k*dx-b.x) LL va = (a.x-b.x)*dy-(a.y-b.y)*dx; if (va==0) return 0; LL vb = (a.y-b.y)*(c.x-b.x)-(a.x-b.x)*(c.y-b.y); if (va<0) vb=-vb; if (vb>0) return 0; dx=a.x-b.x; dy=a.y-b.y; // (b.y+k*dy-d.y)*(c.x-d.x) = (c.y-d.y)*(b.x+k*dx-d.x) va = (c.x-d.x)*dy-(c.y-d.y)*dx; if (va==0) return 0; vb = (c.y-d.y)*(b.x-d.x)-(c.x-d.x)*(b.y-d.y); if (va<0) vb=-vb; if (vb>0) return 0; return 1; } Point pp[16]; char dp[1<<12][12][12]; int mk[12][12]; char ck[12][12][12][12]; int gn; char dfs(int m, int s, int e) { if (m==0) return 0; if (dp[m][s][e]!=-1) return dp[m][s][e]; char r = gn, t; int i, j; for (i=0; i<gn; i++) if ((1<<i)&m) { t=dfs(m&mk[e][i], e, i)+1; r=min(r, t); for (j=0; j<gn; j++) if (j!=i && ck[s][e][i][j]) { t=dfs(m&mk[i][j], i, j)+1; r=min(r, t); } } dp[m][s][e]=r; return r; } int main() { int n, i, j, k, m, i1, j1, mm, r; scanf("%d", &n); if (n==1) { printf("1\n"); return 0; } mm=(1<<n)-1; for (i=0; i<n; i++) scanf("%d %d", &pp[i].x,&pp[i].y); for (i=0; i<n; i++) for (j=i+1; j<n; j++) { m=0; for (k=0; k<n; k++) { if (k==i||k==j) m|=(1<<k); else if (inseg(pp[i], pp[j], pp[k])) m|=(1<<k); } m=mm&(~m); mk[i][j]=mk[j][i]=m; } memset(dp, 0xff, sizeof(dp)); for (i=0; i<n; i++) for (j=0; j<n; j++) { for (i1=0; i1<n; i1++) for (j1=0; j1<n; j1++) { ck[i][j][i1][j1]=cross(pp[i], pp[j], pp[i1], pp[j1]); // if (ck[i][j][i1][j1]) printf("fit %d,%d %d,%d\n", i, j, i1, j1); } } r=n+1; gn=n; for (i=0; i<n; i++) for (j=0; j<n; j++) if (i!=j) { // printf("try %d,%d %x\n", i, j, mk[i][j]); r=min(r, 1+dfs(mk[i][j], i, j)); } printf("%d\n", r); return 0; }