oj.uz

답안 #677492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677492 2023-01-03T13:26:07 Z vjudge1 Printed Circuit Board (CEOI12_circuit) C++17
5 / 100
 91 ms 29032 KB 
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int n;
int X[maxn];
int Y[maxn];
map<ii, int> M;
vector<int> ans;
int sol[maxn];
ii P[maxn];

ll cross(ii p1, ii p2, ii p3) {return (ll)p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);}

ll dist(ii p1) {
	return (ll)p1.x * p1.x + p1.y * p1.y;
}

struct line {
	ii pL, pR;
	friend bool operator<(line l1, line l2) {
		if(dist(l1.pR) == dist(l2.pR)) 
			return dist(l1.pL) < dist(l2.pL);
		return dist(l1.pR) < dist(l2.pR);
	}
};

struct event {
	line l;
	ii p;
	int open;
	friend bool operator<(event a, event b) {
		if(a.p == b.p) return a.open > b.open;
		if(cross({0, 0}, a.p, b.p) == 0) return a.p.x > b.p.x;
		return cross({0, 0}, a.p, b.p) < 0;
	}
};

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
	X[n] = X[0];
	Y[n] = Y[0];
	
	vector<event> sweep;
	for(int i = 0;i < n;i++) {
		line l;
		l.pL = {X[i], Y[i]};
		l.pR = {X[i + 1], Y[i + 1]};
		if(cross({0, 0}, l.pL, l.pR) > 0) swap(l.pL, l.pR);
		event e;
		e.l = l, e.p = l.pL, e.open = 1;
		sweep.pb(e);
		e.p = l.pR, e.open = 0;
		sweep.pb(e);
	}
	 
	sort(all(sweep));
	set<line> s;
	line l1, l2;
	l1.pL = P[3], l1.pR = P[4];
	l2.pL = P[1], l2.pR = P[2];
	
	for(auto e : sweep) {
		if(e.open == 1) {
			if(s.size() == 0) sol[M[e.p]] = 1;
			else {
				line l = *s.begin();
				if(e.l < l) sol[M[e.p]] = 1;
			}
			s.insert(e.l);
		} else {
			if(s.size() == 0) sol[M[e.p]] = 1;
			else {
				line l = *s.begin();
				if(l.pR == e.p) sol[M[e.p]] = 1;
				s.erase(s.find(e.l));
			}
		}
	}
	
	for(int i = 0;i < n;i++) 
		if(sol[i] == 1) ans.pb(i);
	
	printf("%d\n", (int)ans.size());
	for(int i : ans) printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circuit.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Runtime error 3 ms 852 KB Execution killed with signal 6
3 Correct 3 ms 872 KB Output is correct
4 Incorrect 3 ms 1000 KB Output isn't correct
5 Runtime error 10 ms 3536 KB Execution killed with signal 6
6 Runtime error 9 ms 3528 KB Execution killed with signal 6
7 Runtime error 17 ms 6332 KB Execution killed with signal 6
8 Runtime error 8 ms 2960 KB Execution killed with signal 6
9 Runtime error 7 ms 3148 KB Execution killed with signal 6
10 Runtime error 8 ms 3536 KB Execution killed with signal 6
11 Runtime error 10 ms 3776 KB Execution killed with signal 6
12 Incorrect 16 ms 3948 KB Output isn't correct
13 Runtime error 25 ms 9216 KB Execution killed with signal 6
14 Incorrect 32 ms 7496 KB Output isn't correct
15 Incorrect 41 ms 8496 KB Output isn't correct
16 Runtime error 84 ms 28860 KB Execution killed with signal 6
17 Runtime error 91 ms 29032 KB Execution killed with signal 6
18 Runtime error 46 ms 18608 KB Execution killed with signal 11
19 Runtime error 43 ms 18508 KB Execution killed with signal 11
20 Runtime error 83 ms 18636 KB Execution killed with signal 11