103382024-03-31 18:29:35111Úthálózatbővítéscpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Időlimit túllépés600ms13024 KiB
subtask210/10
3Elfogadva3ms3904 KiB
4Elfogadva3ms3988 KiB
5Elfogadva3ms4268 KiB
6Elfogadva6ms4520 KiB
7Elfogadva9ms4944 KiB
subtask30/20
8Elfogadva3ms5076 KiB
9Elfogadva3ms4980 KiB
10Elfogadva18ms5460 KiB
11Elfogadva412ms6912 KiB
12Időlimit túllépés564ms6476 KiB
13Időlimit túllépés578ms11468 KiB
14Időlimit túllépés559ms19156 KiB
15Időlimit túllépés537ms11884 KiB
16Időlimit túllépés561ms12624 KiB
17Időlimit túllépés559ms16224 KiB
subtask40/10
18Elfogadva3ms11812 KiB
19Elfogadva287ms12508 KiB
20Időlimit túllépés566ms12480 KiB
21Időlimit túllépés569ms12644 KiB
22Időlimit túllépés577ms12424 KiB
subtask50/30
23Elfogadva30ms12756 KiB
24Időlimit túllépés598ms13460 KiB
25Elfogadva4ms13108 KiB
26Elfogadva8ms13224 KiB
27Időlimit túllépés578ms13372 KiB
28Időlimit túllépés546ms14388 KiB
29Időlimit túllépés565ms16060 KiB
30Időlimit túllépés558ms16880 KiB
31Időlimit túllépés558ms17440 KiB
32Időlimit túllépés563ms21008 KiB
subtask60/30
33Időlimit túllépés561ms21852 KiB
34Időlimit túllépés564ms22744 KiB
35Időlimit túllépés566ms31332 KiB
36Időlimit túllépés550ms33508 KiB
37Időlimit túllépés554ms33440 KiB
38Időlimit túllépés550ms33444 KiB
39Időlimit túllépés555ms33496 KiB
40Időlimit túllépés536ms33440 KiB
41Időlimit túllépés572ms33444 KiB
42Időlimit túllépés600ms26596 KiB