Submission #246583

#	Time	Username	Problem	Language	Result	Execution time	Memory
246583		vanic	Relay (COI16_relay)	C++14	37 / 100	2082 ms	3312 KiB

relay

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#include <bitset>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int n, m;
vector < pair < int, int > > brod;
vector < pair < int, int > > otok;
bitset < maxn > bio;
bitset < maxn > prvo;

ll ccw(pair < ll, ll > a, pair < ll, ll > b, pair < ll, ll > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}

bool sijece(pair < int, int > a, pair < int, int > b, pair < int, int > c, pair < int, int > d){
	ll a1, b1, c1, d1;
	a1=ccw(a, b, c);
	b1=ccw(a, b, d);
	c1=ccw(c, d, a);
	d1=ccw(c, d, b);
	if(((a1>0 && b1<0) || (a1<0 && b1>0)) && ((c1>0 && d1<0) || (c1<0 && d1>0))){
		return 1;
	}
	return 0;
}

void rijesi(int x){
	pair < int, int > l, d;
	bool p=0;
	ll y;
	for(int i=0; i<m; i++){
		y=ccw(otok[i], otok[(i+1)%m], brod[x]);
//		cout << y << " ";
		if(y<=0){
			if(!p){
				l=otok[i];
				p=1;
			}
		}
		else{
			if(p){
				d=otok[i];
				p=0;
			}
		}
	}
	if(p && ccw(otok[0], otok[1], brod[x])>0){
		d=otok[0];
	}
/*	cout << endl;
	cout << l.first << " " << l.second << '\n';
	cout << d.first << " " << d.second << '\n';*/
//	cout << "sijece\n";
	for(int i=0; i<n; i++){
		if(!bio[i] && !sijece(l, d, brod[x], brod[i])){
			bio[i]=1;
//			cout << brod[i].first << " " << brod[i].second << '\n';
		}
	}
//	cout << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		brod.push_back({a, b});
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		otok.push_back({a, b});
	}
	bio[0]=1;
	rijesi(0);
	prvo=bio;
	for(int i=1; i<n; i++){
		if(prvo[i]){
			rijesi(i);
		}
	}
	cout << bio.count()-1 << '\n';
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 19 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43