103382024-03-31 18:29:35111Úthálózatbővítéscpp17Time limit exceeded 10/100600ms33508 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

struct P{
	int x,y;
};

bool operator==(P a,P b){
	return a.x==b.x&&a.y==b.y;
}

bool operator<(P a,P b){
	return a.x<b.x||a.x==b.x&&a.y<b.y;
}

P operator+(P a,P b){
	return P{a.x+b.x,a.y+b.y};
}

P operator-(P a,P b){
	return P{a.x-b.x,a.y-b.y};
}

istream&operator>>(istream&is,P&p){
	return is>>p.x>>p.y;
}

ostream&operator<<(ostream&os,P p){
	return os<<'('<<p.x<<','<<p.y<<')';
}

int sign(int x){
	return (x>0)-(x<0);
}

int cross(P a,P b){
	return a.x*b.y-b.x*a.y;
}

int orient(P a,P b,P c){
	return sign(cross(a-b,c-b));
}

int test(pair<P,P>a,pair<P,P>b){
	if(a.first==b.first||a.first==b.second||a.second==b.first||a.second==b.second){
		return false;
	}
	int o1=orient(a.first,a.second,b.first);
	int o2=orient(a.first,a.second,b.second);
	int o3=orient(b.first,b.second,a.first);
	int o4=orient(b.first,b.second,a.second);
	return o1!=o2&&o3!=o4;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<pair<P,int>>v(N+1);
	for(int i=0;i<=N;i++){
		cin>>v[i].first;
		v[i].second=i;
	}
	vector<pair<P,P>>e;
	for(int i=1;i<=N;i++){
		e.emplace_back(v[0].first,v[i].first);
	}
	for(int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		e.emplace_back(v[a].first,v[b].first);
	}
	for(auto&p:e){
		if(p.second<p.first){
			swap(p.first,p.second);
		}
	}
	vector<int>ans(N,1);
	for(int i=0;i<N;i++){
		for(int j=N;j<e.size();j++){
			if(test(e[i],e[j])){
				ans[i]=0;
			}
		}
	}
	cout<<count(ans.begin(),ans.end(),1)<<'\n';
	for(int i=0;i<N;i++){
		if(ans[i]){
			cout<<i+1<<' ';
		}
	}
	cout<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
2Time limit exceeded600ms13024 KiB
subtask210/10
3Accepted3ms3904 KiB
4Accepted3ms3988 KiB
5Accepted3ms4268 KiB
6Accepted6ms4520 KiB
7Accepted9ms4944 KiB
subtask30/20
8Accepted3ms5076 KiB
9Accepted3ms4980 KiB
10Accepted18ms5460 KiB
11Accepted412ms6912 KiB
12Time limit exceeded564ms6476 KiB
13Time limit exceeded578ms11468 KiB
14Time limit exceeded559ms19156 KiB
15Time limit exceeded537ms11884 KiB
16Time limit exceeded561ms12624 KiB
17Time limit exceeded559ms16224 KiB
subtask40/10
18Accepted3ms11812 KiB
19Accepted287ms12508 KiB
20Time limit exceeded566ms12480 KiB
21Time limit exceeded569ms12644 KiB
22Time limit exceeded577ms12424 KiB
subtask50/30
23Accepted30ms12756 KiB
24Time limit exceeded598ms13460 KiB
25Accepted4ms13108 KiB
26Accepted8ms13224 KiB
27Time limit exceeded578ms13372 KiB
28Time limit exceeded546ms14388 KiB
29Time limit exceeded565ms16060 KiB
30Time limit exceeded558ms16880 KiB
31Time limit exceeded558ms17440 KiB
32Time limit exceeded563ms21008 KiB
subtask60/30
33Time limit exceeded561ms21852 KiB
34Time limit exceeded564ms22744 KiB
35Time limit exceeded566ms31332 KiB
36Time limit exceeded550ms33508 KiB
37Time limit exceeded554ms33440 KiB
38Time limit exceeded550ms33444 KiB
39Time limit exceeded555ms33496 KiB
40Time limit exceeded536ms33440 KiB
41Time limit exceeded572ms33444 KiB
42Time limit exceeded600ms26596 KiB