Submission #678838

#	Time	Username	Problem	Language	Result	Execution time	Memory
678838		vjudge1	Printed Circuit Board (CEOI12_circuit)	C++17	15 / 100	255 ms	40596 KiB

circuit

#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 (stderr)

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 / 100