Submission #678831

#	Time	Username	Problem	Language	Result	Execution time	Memory
678831		vjudge1	Printed Circuit Board (CEOI12_circuit)	C++17	10 / 100	202 ms	25252 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);
	
	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);
	}
	
	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;
			}	
	}
	
	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:107:9: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  107 |    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:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%Lf%Lf", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100