oj.uz

답안 #25707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25707 2017-06-23T18:58:23 Z gs14004 Printed Circuit Board (CEOI12_circuit) C++11
75 / 100
 100 ms 5204 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
  
int n;
pi a[100005];
vector<pi> v;
pi tree[270000];
  
int gcd(int x, int y){
	return y ? gcd(y, x%y) : x;
}
  
bool ccw(pi a, pi b){
	return 1ll * b.first * a.second > 1ll * a.first * b.second;
}
  
bool ccw2(pi a, pi b, pi c){
	return ccw(pi(b.first - a.first, b.second - a.second), pi(c.first - a.first, c.second - a.second));
}
  
bool same(pi a, pi b){
	return 1ll * b.first * a.second == 1ll * a.first * b.second;
}
  
struct line{
	int a, b;
	lint c;
};
  
double crs(line a, line b){
	return (1.0 * a.b * b.c - 1.0 * a.c * b.b) / (1.0 * a.a * b.b - 1.0 * a.b * b.a);
}
  
pi compare(pi p, pi q, int r1, int r2){
	if(p.first == -1) return q;
	if(q.first == -1) return p;
	line p1 = {a[p.second].second - a[p.first].second, a[p.first].first - a[p.second].first, 0ll};
	p1.c = - 1ll * p1.a * a[p.first].first - 1ll * p1.b * a[p.first].second;
	line p2 = {a[q.second].second - a[q.first].second, a[q.first].first - a[q.second].first, 0ll};
	p2.c = - 1ll * p2.a * a[q.first].first - 1ll * p2.b * a[q.first].second;
	line p3 = {v[r1].second + v[r2].second, -v[r1].first - v[r2].first, 0ll};
	if(crs(p1, p3) < crs(p2, p3)) return p;
	return q;
}
  
void add(int s, int e, int ps, int pe, int p, pi v){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		tree[p] = compare(tree[p], v, ps, pe + 1);
		return;
	}
	int pm = (ps + pe) / 2;
	add(s, e, ps, pm, 2*p, v);
	add(s, e, pm+1, pe, 2*p+1, v);
}
  
pi query(int pos, int ps, int pe, int p){
	if(ps == pe) return tree[p];
	int pm = (ps + pe) / 2;
	if(pos <= pm) return compare(tree[p], query(pos, ps, pm, 2*p), pos, pos + 1);
	return compare(tree[p], query(pos, pm+1, pe, 2*p+1), pos, pos + 1);
}

pi queries[100005];

int main(){
	fill(tree, tree + 270000, pi(-1, -1));
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first, &a[i].second);
		int g = gcd(a[i].first, a[i].second);
		v.push_back(pi(a[i].first / g, a[i].second / g));
	}
	a[n] = a[0];
	sort(v.begin(), v.end(), ccw);
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for(int i=0; i<n; i++){
		int s = lower_bound(v.begin(), v.end(), a[i], ccw) - v.begin();
		int e = lower_bound(v.begin(), v.end(), a[i+1], ccw) - v.begin();
		if(s == e) continue;
		pi val(i, (i+1)%n);
		if(s > e){
			swap(s, e);
			swap(val.first, val.second);
		}
		add(s, e-1, 0, v.size()-2, 1, val);
	}
	for(int i=0; i<v.size()-1; i++){
		queries[i] = query(i, 0, v.size()-2, 1);
	}
	vector<int> v2;
	for(int i=0; i<n; i++){
		int p = lower_bound(v.begin(), v.end(), a[i], ccw) - v.begin();
		bool bad = 0;
		if(p != v.size()-1){
			pi t = queries[p];
			if(ccw2(a[t.second], a[t.first], a[i])){
				bad = 1;
			}
		}
		if(p != 0){
			pi t = queries[p-1];
			if(ccw2(a[t.second], a[t.first], a[i])){
				bad = 1;
			}
		}
		if(!bad) v2.push_back(i+1);
	}
	printf("%d\n",v2.size());
	for(auto &i : v2){
		printf("%d ",i);
	}
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:107:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size()-1; i++){
               ~^~~~~~~~~~~
circuit.cpp:114:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p != v.size()-1){
      ~~^~~~~~~~~~~~~
circuit.cpp:128:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",v2.size());
                ~~~~~~~~~^
circuit.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circuit.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
75.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 6 ms 2536 KB Output is correct
3 Correct 6 ms 2596 KB Output is correct
4 Correct 8 ms 2896 KB Output is correct
5 Correct 19 ms 2972 KB Output is correct
6 Correct 19 ms 2972 KB Output is correct
7 Correct 41 ms 3224 KB Output is correct
8 Correct 19 ms 3224 KB Output is correct
9 Correct 16 ms 3224 KB Output is correct
10 Correct 22 ms 3224 KB Output is correct
11 Correct 32 ms 3224 KB Output is correct
12 Correct 43 ms 3336 KB Output is correct
13 Correct 62 ms 3592 KB Output is correct
14 Correct 61 ms 3716 KB Output is correct
15 Correct 77 ms 3972 KB Output is correct
16 Execution timed out 140 ms 5136 KB Time limit exceeded
17 Execution timed out 212 ms 5204 KB Time limit exceeded
18 Execution timed out 40 ms 5204 KB Time limit exceeded (wall clock)
19 Execution timed out 42 ms 5204 KB Time limit exceeded (wall clock)
20 Execution timed out 54 ms 5204 KB Time limit exceeded (wall clock)