10338 | 2024-03-31 18:29:35 | 111 | Úthálózatbővítés | cpp17 | Time limit exceeded 10/100 | 600ms | 33508 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1824 KiB | ||||
2 | Time limit exceeded | 600ms | 13024 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Accepted | 3ms | 3904 KiB | ||||
4 | Accepted | 3ms | 3988 KiB | ||||
5 | Accepted | 3ms | 4268 KiB | ||||
6 | Accepted | 6ms | 4520 KiB | ||||
7 | Accepted | 9ms | 4944 KiB | ||||
subtask3 | 0/20 | ||||||
8 | Accepted | 3ms | 5076 KiB | ||||
9 | Accepted | 3ms | 4980 KiB | ||||
10 | Accepted | 18ms | 5460 KiB | ||||
11 | Accepted | 412ms | 6912 KiB | ||||
12 | Time limit exceeded | 564ms | 6476 KiB | ||||
13 | Time limit exceeded | 578ms | 11468 KiB | ||||
14 | Time limit exceeded | 559ms | 19156 KiB | ||||
15 | Time limit exceeded | 537ms | 11884 KiB | ||||
16 | Time limit exceeded | 561ms | 12624 KiB | ||||
17 | Time limit exceeded | 559ms | 16224 KiB | ||||
subtask4 | 0/10 | ||||||
18 | Accepted | 3ms | 11812 KiB | ||||
19 | Accepted | 287ms | 12508 KiB | ||||
20 | Time limit exceeded | 566ms | 12480 KiB | ||||
21 | Time limit exceeded | 569ms | 12644 KiB | ||||
22 | Time limit exceeded | 577ms | 12424 KiB | ||||
subtask5 | 0/30 | ||||||
23 | Accepted | 30ms | 12756 KiB | ||||
24 | Time limit exceeded | 598ms | 13460 KiB | ||||
25 | Accepted | 4ms | 13108 KiB | ||||
26 | Accepted | 8ms | 13224 KiB | ||||
27 | Time limit exceeded | 578ms | 13372 KiB | ||||
28 | Time limit exceeded | 546ms | 14388 KiB | ||||
29 | Time limit exceeded | 565ms | 16060 KiB | ||||
30 | Time limit exceeded | 558ms | 16880 KiB | ||||
31 | Time limit exceeded | 558ms | 17440 KiB | ||||
32 | Time limit exceeded | 563ms | 21008 KiB | ||||
subtask6 | 0/30 | ||||||
33 | Time limit exceeded | 561ms | 21852 KiB | ||||
34 | Time limit exceeded | 564ms | 22744 KiB | ||||
35 | Time limit exceeded | 566ms | 31332 KiB | ||||
36 | Time limit exceeded | 550ms | 33508 KiB | ||||
37 | Time limit exceeded | 554ms | 33440 KiB | ||||
38 | Time limit exceeded | 550ms | 33444 KiB | ||||
39 | Time limit exceeded | 555ms | 33496 KiB | ||||
40 | Time limit exceeded | 536ms | 33440 KiB | ||||
41 | Time limit exceeded | 572ms | 33444 KiB | ||||
42 | Time limit exceeded | 600ms | 26596 KiB |