oj.uz

답안 #678838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678838 2023-01-06T16:39:44 Z vjudge1 Printed Circuit Board (CEOI12_circuit) C++17
15 / 100
 100 ms 40596 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define pb push_back

using namespace std;

typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

const int N = 1e5 + 10;
const ld INF = 1e13;
const ld DIFF = 1e-7;

int n, on[N], CNT;
ld ang = 1;

ld abs2(ld a){
	if(a < 0) return -a;
	return a;
}

bool eq(ld a, ld b){
	return abs2(a - b) <= DIFF;
}

struct line{
	ld a, b;
	bool ver;
	line(ld x1, ld y1, ld x2, ld y2){
		ver = false;
		if(x1 != x2){
			a = (y2 - y1) / (x2 - x1);
			b = y1 - a * x1;
		} else {
			a = x1;
			b = 0;
			ver = true;
		}
	}
};

ld inter(line a){if(a.ver) return a.a; else if(eq(ang, a.a)) return -INF; return a.b / (ang - a.a); }
bool operator< (const line &a, const line &b) { return inter(a) < inter(b); }

struct dot{
	ld x, y;

	dot(){};
	dot(int a, int b){ x = a; y = b; };
	bool operator< (dot b){	return (y / x) > (b.y / b.x) + DIFF || (eq(y / x, b.y / b.x) && x > b.x); };
};

dot pol[N];

vector<pair<dot, int>> cs;
vector<line> ln;
vector<int> edge[N], ans;

set<line> s;

bool comp(pair<dot, int> a, pair<dot, int> b){ return a.X < b.X; }

void debug(line x){
	printf("(%.3LF, %.3LF) %.3Lf\n", x.a, x.b, inter(x));
}

int main(){
	scanf("%d", &n);

    map<pair<int, int>, int> mini;

    vector<int> xxx(n), yyy(n);

	for(int i = 0; i < n; i++){
		ld x, y;
		scanf("%Lf%Lf", &x, &y);
		cs.pb({dot(x, y), i});
		pol[i] = dot(x, y);

		int xx = x, yy = y;
		xx /= __gcd((int) x,  (int) y);
		yy /= __gcd((int) x,  (int) y);

		xxx[i] = x;
		yyy[i] = y;

		if (mini[{xx, yy}] == 0) mini[{xx, yy}] = x;
		else mini[{xx, yy}] = min(mini[{xx, yy}], (int) x);
	}

	for(int i = 0; i < n; i++){
		edge[i].pb(ln.size());
		edge[(i + 1) % n].pb(ln.size());
		ln.pb(line(pol[i].x, pol[i].y, pol[(i + 1) % n].x, pol[(i + 1) % n].y));
	}

	sort(cs.begin(), cs.end(), comp);

	for(pair<dot, int> par : cs){
		dot d = par.X;
		int ind = par.Y;

		//printf("%d\n", ind);

		ang = d.y / d.x;

		for(int i : edge[ind])
			if(on[i]){
				s.erase(ln[i]);
				//if(i == 2) debug(ln[i]);
			}

		if(s.empty() || d.x + DIFF < inter(*s.begin())){
			ans.pb(ind);
		}

		if(!s.empty() && ind == 1){
			line l = *(s.begin());
			//debug(l);
		}

		for(int i : edge[ind])
			if(!on[i]){
				s.insert(ln[i]);
				on[i] = 1;
			}
	}

	vector<int> newAns;
	for (int ind : ans) {
        int g = __gcd(xxx[ind], yyy[ind]);
        if (mini[{xxx[ind] / g, yyy[ind] / g}] == xxx[ind]) newAns.push_back(ind);
	}

	ans = newAns;
	sort(ans.begin(), ans.end());
	printf("%d\n", (int) ans.size());
	for(int i = 0; i < (int) ans.size(); i++)
            printf("%d ", ans[i] + 1);
	printf("\n");
	return 0;
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:121:9: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  121 |    line l = *(s.begin());
      |         ^
circuit.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circuit.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%Lf%Lf", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Incorrect 3 ms 2900 KB Output isn't correct
3 Correct 6 ms 3412 KB Output is correct
4 Correct 7 ms 3668 KB Output is correct
5 Incorrect 23 ms 5388 KB Output isn't correct
6 Incorrect 20 ms 5388 KB Output isn't correct
7 Incorrect 41 ms 8200 KB Output isn't correct
8 Incorrect 21 ms 4624 KB Output isn't correct
9 Incorrect 17 ms 5112 KB Output isn't correct
10 Incorrect 20 ms 5388 KB Output isn't correct
11 Incorrect 23 ms 5636 KB Output isn't correct
12 Correct 32 ms 8200 KB Output is correct
13 Incorrect 68 ms 10192 KB Output isn't correct
14 Incorrect 60 ms 13620 KB Output isn't correct
15 Incorrect 80 ms 15728 KB Output isn't correct
16 Execution timed out 174 ms 28776 KB Time limit exceeded
17 Execution timed out 255 ms 28864 KB Time limit exceeded
18 Execution timed out 106 ms 40596 KB Time limit exceeded
19 Execution timed out 106 ms 40584 KB Time limit exceeded
20 Execution timed out 126 ms 40556 KB Time limit exceeded