QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#653712 | #7511. Planar Graph | ucup-team5071# | RE | 0ms | 0kb | C++20 | 5.5kb | 2024-10-18 20:32:01 | 2024-10-18 20:32:09 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pt=ll;
constexpr pt eps =0;
template<typename T> struct point{
T x,y;
bool operator==(const point &a)const{return {abs(x-a.x)<=eps&&abs(y-a.y)<=eps};}
bool operator<(const point &a)const{if(abs(x-a.x)<=eps)return y<a.y-eps;return x<a.x-eps;}
bool operator>(const point &a)const{return !(*this<a||*this==a);}
point operator+(const point &a)const{return {x+a.x,y+a.y};}
point operator-(const point &a)const{return {x-a.x,y-a.y};}
point operator-()const{return {-x,-y};}
point operator*(const T k)const {return {k*x,k*y};};
T operator*(const point &a)const{return x*a.x+y*a.y;}
T operator^(const point &a)const{return x*a.y-y*a.x;}
int toleft(const point &a)const{const auto t=(*this)^a;return (t>eps)-(t<-eps);}
T len2() const{return (*this)*(*this);}
};
using Point = point<ll>;
struct argcmp
{
bool operator()(const Point &a,const Point &b)const{
const auto quad=[](const Point &a)
{
if(a.y<-eps)return 1;
if(a.y>eps)return 4;
if(a.x<-eps)return 5;
if(a.x>eps)return 3;
return 2;
};
const int qa=quad(a),qb=quad(b);
if(qa!=qb)return qa<qb;
const auto t=a^b;
return t>eps;
}
};
template<typename T> struct line{
point<T> p,v;
int toleft(const point<T> &a)const{return v.toleft(a-p);}
};
using Line = line<pt>;
template<typename T> struct segment{
point<T> a,b;
int is_on(const point<T> &p)const{
if(p==a||p==b)return -1;
return (p-a).toleft(p-b)==0&& (p-a)*(p-b)<-eps;
}
int is_inter(const segment<T> &s)const{
if(is_on(s.a)||is_on(s.b)||s.is_on(a)||s.is_on(b))return -1;
const line<T> l{a,b-a},ls{s.a,s.b-s.a};
return l.toleft(s.a)*l.toleft(s.b)==-1&&ls.toleft(a)*ls.toleft(b)==-1;
}
};
using Segment = segment<pt>;
using pii =pair<int,int>;
int main()
{
int n,m,e;
cin>>n>>m>>e;
vector<Point>a(n);
for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;
for(int i=0;i<m;i++)cin>>a[i+n].x>>a[i+n].y;
vector<vector<int>> edge_id(n+m,vector<int>(n+m,-1));
vector<pair<int,int>> edges(e);
vector<vector<pair<int,int>>> ve(n+m);
for(int i=0;i<e;i++){
int x,y;cin>>x>>y;
x--,y--;
edges[i]=make_pair(x,y);
edge_id[x][y]=i;
edge_id[y][x]=i;
ve[x].emplace_back(y,1);
ve[y].emplace_back(x,1);
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n+m;j++)if(edge_id[i][j]==-1){
int flag=1;
Segment now{a[i],a[j]};
for(auto [x,y]:edges)if(now.is_inter(Segment{a[x],a[y]})>0)flag=0;
if(flag){
ve[i].emplace_back(j,0);
ve[j].emplace_back(i,0);
}
}
}
vector<vector<vector<pii>>> ve2(n+m);
vector<vector<int>> point_id(n+m,vector<int>(n+m,-1));
for(int i=0;i<n+m;i++){
sort(ve[i].begin(),ve[i].end(),[&](pii x,pii y){
return argcmp()(a[x.first]-a[i],a[y.first]-a[i]);
});
// cout<<"i="<<i<<endl;
// for(auto [x,y]:ve[i])cout<<x<<"/"<<y<<" ";;cout<<endl;
int cnt=0;
for(auto [to,type]:ve[i])cnt+=type;
if(cnt<=1){
ve2[i].resize(1);
for(auto [to,type]:ve[i])point_id[i][to]=0;
}
else{
int j=0;
while(ve[i][j].second==0)j++;
int pr=-1,cnt=0;
for(int tt=0;tt<ve[i].size();tt++,j=(j+1)%ve[i].size()){
if(ve[i][j].second==1){
pr=cnt;
cnt++;
}
point_id[i][ve[i][j].first]=pr;
// cout<<"i="<<i<<" cnt="<<cnt<<" j="<<j<<" to="<<ve[i][j].first<<" pr="<<pr<<endl;
}
ve2[i].resize(cnt);
}
// cout<<"give point_id i="<<i<<endl;
}
// cout<<"siz :";for(int i=0;i<n+m;i++)cout<<ve2[i].size()<<" ";;cout<<endl;
string ans(e,'0');
for(int i=0;i<n+m;i++){
for(auto [to,type]:ve[i]){
// cout<<"i="<<i<<" to="<<to<<" type="<<type<<endl;
if(type){
// cout<<"id1="<<point_id[i][to]<<" id2="<<point_id[to][i]<<endl;
ve2[i][point_id[i][to]].emplace_back(to,(point_id[to][i]-1+ve2[to].size())%ve2[to].size());
ve2[i][(point_id[i][to]-1+ve2[i].size())%ve2[i].size()].emplace_back(to,point_id[to][i]);
}
else{
// cout<<"id1="<<point_id[i][to]<<" id2="<<point_id[to][i]<<endl;
ve2[i][point_id[i][to]].emplace_back(to,point_id[to][i]);
}
}
// cout<<"ve2 i="<<i<<" ok"<<endl;
}
vector<vector<int>> vis(n+m,vector<int>(n+m));
for(int i=n;i<n+m;i++){
queue<pair<int,int>>qu;
if(!vis[i][0])qu.push({i,0}),vis[i][0]=1;
while(!qu.empty()){
auto [x,id]=qu.front();qu.pop();
// cout<<"vis x="<<x<<" id="<<id<<endl;
assert(id<ve2[x].size());
for(auto [y,idy]:ve2[x][id]){
// cout<<"e_id="<<edge_id[x][y]<<" x="<<x<<" y="<<y<<endl;
if(edge_id[x][y]!=-1)ans[edge_id[x][y]]='1';
if(!vis[y][idy]){
vis[y][idy]=1;
qu.push({y,idy});
}
}
}
// cout<<"ok i="<<i<<endl;
}
cout<<ans<<"\n";
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3