#include using namespace std; vector p(3'001,-1); int cnt[3'001]; int ans,cnt_ans; struct Point { int x, y; }; vector> lines; int find(int x){ if(p[x] < 0 ) return x; return p[x] = find(p[x]); } bool uni(int u,int v){ u = find(u); v = find(v); if(u == v) return false; if(p[v] < p[u]) swap(u,v); if(p[u] == p[v]) p[u] --; p[v] = u; cnt[u] +=cnt[v]; return true; } // i j k // AB_X AB_Y 0 // AC_X AC_Y 0 // = k(AB_X * AC_Y - AB_Y * AC_X) int ccw(Point a, Point b, Point c){ int AB_X = b.x - a.x; int AB_Y = b.y - a.y; int AC_X = c.x - a.x; int AC_Y = c.y - a.y; int val = AB_X * AC_Y - AB_Y * AC_X; // AB X AC if(val < 0 ) return -1; else if (val > 0 ) return 1; return 0; } bool isonline (Point a, Point b, Point c){ return min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x) && min(a.y,b.y) <= c.y && c.y <= max(a.y,b.y); } bool isIntersect(Point a, Point b, Point c,Point d){ int ab_c = ccw(a,b,c); int ab_d = ccw(a,b,d); int cd_a = ccw(c,d,a); int cd_b = ccw(c,d,b); if(ab_c * ab_d < 0 && cd_a * cd_b <0 ) return true; if(ab_c == 0 && isonline(a,b,c)) return true; if(ab_d == 0 && isonline(a,b,d)) return true; if(cd_a == 0 && isonline(c,d,a)) return true; if(cd_b == 0 && isonline(c,d,b)) return true; return false; } int main(void){ cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n ; fill(cnt,cnt+n,1); for(int i = 0 ; i < n ; i ++){ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; lines.push_back({{x1,y1},{x2,y2}}); } for(int i = 0 ; i < n - 1 ; i ++){ for(int j = i+1; j < n; j ++){ auto s = lines[i]; auto n = lines[j]; if(isIntersect(s.first,s.second,n.first,n.second)){ uni(i,i+1); } } } for(int i = 0 ; i < n ; i++){ if(p[i] < 0) ans ++; } cnt_ans = *max_element(cnt,cnt+n); cout << ans << "\n"; cout << cnt_ans; }

제출 #80623

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: