Submission #677609

#	Time	Username	Problem	Language	Result	Execution time	Memory
677609		vjudge1	Printed Circuit Board (CEOI12_circuit)	C++14	5 / 100	151 ms	57128 KiB

circuit

#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define pld pair<ld, ld>

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
const ld eps = 1e-10;

int ccw(pll a, pll b, pll c){
	ll val = a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
	if(val > 0) return 1;
	if(val == 0) return 0;
	return -1; 
}

vpll arr;
vi cv;
int pos[MAXN];
matrix op;


bool cmp(int ai, int bi){
	pll a = arr[ai], b = arr[bi];
	int cv = ccw({0, 0}, a, b);
	if(cv == 0) return a.X < b.X;
	return cv > 0;
}

bool cmp2(vi a, vi b){
	if(pos[a[0]] == pos[b[0]]){
		return pos[a[1]] < pos[b[1]];
	}
	return pos[a[0]] < pos[b[0]];
}

bool same(ld a, ld b){
	if(abs(a - b) < eps) return 1;
	return 0;
}

ld dist(pll r){
	return (ld)sqrt((ld)r.X * r.X + (ld)r.Y * r.Y);
}

//s desno od r
ld dis(pld r, pld s){
	if(!same(r.X, s.X) and r.X > s.X) swap(r, s);
	ld val = min(r.X * r.X + r.Y * r.Y, s.X * s.X + s.Y * s.Y);
	val = (ld)sqrt(val);
	if(s.X == r.X or s.Y == r.Y) return val;
	
	ld a = (ld)(s.Y - r.Y) / (ld)(s.X - r.X);
	if(a == 1) return val;
	
	ld b = r.Y - r.X * a;
	ld opx = (ld)(-b) / (ld)((ld)a + (ld)1 / (ld)a);
	
	ld opy = opx * a + b;
	if(opx >= min(r.X, s.X) and opx <= max(r.X, s.X) and opy >= min(r.Y, s.Y) and opy <= max(r.Y, s.Y)){
		val = min(val, (ld)sqrt(opx * opx + opy * opy));	
	}
	
	return val;
}

struct cmp3{	
	bool operator()(ld a, ld b){
		//if(abs(a - b) < eps) return 1;
		return a < b;
	}	
};


multiset<ld, cmp3> ud;

bool bgoreq(ld a, ld b){
	if(abs(a - b) < eps) return 1;
	return a > b;	
}

void solve(){
	int n;
	cin >> n;
	arr.resize(n);
	REP(i, n) cin >> arr[i].X >> arr[i].Y, cv.PB(i);
	sort(all(cv), cmp);
	REP(i, n) pos[cv[i]] = i;
	REP(i, n){
		int nx = (i + 1) % n;
		int ni = i;
		if(pos[i] > pos[nx]) swap(ni, nx);
		op.PB({ni, nx, 1});
		op.PB({nx, (ni + 1) * 1000, -1});
	}
	sort(all(op), cmp2);
	
	vi sol; sol.clear();
	for(auto &x : op){
		if(x[2] == -1){
			x[1] /= 1000;
			x[1]--;
		}
		ld val = dis(arr[x[0]], arr[x[1]]);
		
		if(x[2] == 1){
			if(ud.empty() or bgoreq(*ud.begin(), dist(arr[x[0]]))) sol.PB(x[0] + 1);
			ud.insert(val);
		}else{
			ud.erase(ud.find(val));
			if(ud.empty() or bgoreq(*ud.begin(), dist(arr[x[0]]))) sol.PB(x[0] + 1);
		}
	}
	
	if(sol.empty()){
		cout << 0;
		return;
	}
	sort(all(sol));
	sol.erase(unique(all(sol)), sol.end());
	cout << sol.size() << "\n";
	for(auto &x : sol) cout << x << " ";
	cout << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

• Subtask 1: 5 / 100