oj.uz

답안 #677609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677609 2023-01-03T22:42:37 Z vjudge1 Printed Circuit Board (CEOI12_circuit) C++14
5 / 100
 100 ms 57128 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 3 ms 468 KB Output isn't correct
3 Runtime error 3 ms 1364 KB Execution killed with signal 11
4 Runtime error 12 ms 1544 KB Execution killed with signal 11
5 Runtime error 7 ms 3336 KB Execution killed with signal 11
6 Runtime error 7 ms 3348 KB Execution killed with signal 11
7 Runtime error 15 ms 6096 KB Execution killed with signal 11
8 Runtime error 6 ms 2680 KB Execution killed with signal 11
9 Runtime error 8 ms 2928 KB Execution killed with signal 11
10 Runtime error 8 ms 3344 KB Execution killed with signal 11
11 Runtime error 9 ms 3640 KB Execution killed with signal 11
12 Runtime error 15 ms 6140 KB Execution killed with signal 11
13 Runtime error 20 ms 8928 KB Execution killed with signal 11
14 Runtime error 23 ms 11604 KB Execution killed with signal 11
15 Runtime error 34 ms 14476 KB Execution killed with signal 11
16 Runtime error 73 ms 28600 KB Execution killed with signal 11
17 Runtime error 68 ms 28724 KB Execution killed with signal 11
18 Execution timed out 147 ms 56840 KB Time limit exceeded
19 Execution timed out 151 ms 56872 KB Time limit exceeded
20 Execution timed out 127 ms 57128 KB Time limit exceeded