#include #include using namespace std; struct Segment { int id; int x1, y1, x2, y2; }; vector parent; vector group_count; int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int result = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1); if (result > 0) { return 1; // Counter-clockwise } else if (result < 0) { return -1; // Clockwise } else { return 0; // Collinear } } bool isAttached(const Segment& a, const Segment& b) { // Check if segments a and b are attached int ACB = ccw(a.x1, a.y1, a.x2, a.y2, b.x1, b.y1); int ADB = ccw(a.x1, a.y1, a.x2, a.y2, b.x2, b.y2); int CDB = ccw(b.x1, b.y1, b.x2, b.y2, a.x1, a.y1); int CDA = ccw(b.x1, b.y1, b.x2, b.y2, a.x2, a.y2); int minX1 = min(a.x1, a.x2); int maxX1 = max(a.x1, a.x2); int minY1 = min(a.y1, a.y2); int maxY1 = max(a.y1, a.y2); int minX2 = min(b.x1, b.x2); int maxX2 = max(b.x1, b.x2); int minY2 = min(b.y1, b.y2); int maxY2 = max(b.y1, b.y2); if (ACB != ADB && CDB != CDA) { return true; // Segments intersect } if (ACB == 0 || ADB == 0) { // Check if b's endpoints are on segment a return ( (minX1 <= b.x1 && b.x1 <= maxX1 && minY1 <= b.y1 && b.y1 <= maxY1) || (minX1 <= b.x2 && b.x2 <= maxX1 && minY1 <= b.y2 && b.y2 <= maxY1) || (minX2 <= a.x1 && a.x1 <= maxX2 && minY2 <= a.y1 && a.y1 <= maxY2) || (minX2 <= a.x2 && a.x2 <= maxX2 && minY2 <= a.y2 && a.y2 <= maxY2) ); } else if (CDB == 0 || CDA == 0) { // Check if a's endpoints are on segment b return ( (minX1 <= b.x1 && b.x1 <= maxX1 && minY1 <= b.y1 && b.y1 <= maxY1) || (minX1 <= b.x2 && b.x2 <= maxX1 && minY1 <= b.y2 && b.y2 <= maxY1) || (minX2 <= a.x1 && a.x1 <= maxX2 && minY2 <= a.y1 && a.y1 <= maxY2) || (minX2 <= a.x2 && a.x2 <= maxX2 && minY2 <= a.y2 && a.y2 <= maxY2) ); } // Implement the intersection, touching, and collinear checks here return false; // Placeholder } int findParent(int x) { if (parent[x] != x) { parent[x] = findParent(parent[x]); // Path compression } return parent[x]; } int unionSegments(int a, int b) { int rootA = findParent(a); int rootB = findParent(b); if (rootA != rootB) { parent[rootB] = rootA; // Union the two segments group_count[rootA] += group_count[rootB]; // Update group size group_count[rootB] = 0; // Reset the size of the merged group } return 0; } int main(void) { int N; cin >> N; vector segments(N); parent.resize(N); group_count.resize(N, 1); for (int i = 0; i < N; ++i) { segments[i].id = i; cin >> segments[i].x1 >> segments[i].y1 >> segments[i].x2 >> segments[i].y2; parent[i] = i; // Initialize each segment as its own parent } for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (isAttached(segments[i], segments[j])) { if (findParent(i) != findParent(j)) { unionSegments(i, j); } } } } int group_count_result = 0; int max_group_size = 0; for (int i = 0; i < N; ++i) { if (parent[i] == i) { // Count unique parents group_count_result++; max_group_size = max(max_group_size, group_count[i]); } } cout << group_count_result << '\n'; cout << max_group_size << '\n'; return 0; }

제출 #194425

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: