QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260882 | #7804. Intersegment Activation | Geospiza# | RE | 0ms | 0kb | C++20 | 3.1kb | 2023-11-22 16:20:31 | 2023-11-22 16:20:32 |
answer
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define Ma 1000005
#define G 3
#define N 512
#define pb push_back
#define L (1<<21)
#define PLL pair<ll,ll>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
using namespace std;
ll inf=1e18;
ll sgn(double x)
{
if (x>0) return 1;
if (x<0) return -1;
return 0;
}
struct Point{
ll x,y;
bool operator <(Point a)const
{
if (x==a.x)
return y<a.y;
return x<a.x;
}
bool operator == (Point a)const
{
return sgn(x-a.x)==0&&sgn(y-a.y)==0;
}
Point operator -(Point b){
return {x-b.x,y-b.y};
}
Point operator +(Point b){
return {x+b.x,y+b.y};
}
ll operator ^(Point b){
return x*b.y-y*b.x;
}
ll operator *(Point b){
return x*b.x+y*b.y;
}
};
struct Line{
Point s,e;
ll relation(Point p){
ll c=sgn((p-s)^(e-s));
if (c<0) return 1;
else if (c>0) return 2;
return 3;
}
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s))==0;
}
ll linecrossline(Line v){
if ((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
Point crosspoint(Line v){
ll a1=(v.e-v.s)^(s-v.s);
ll a2=(v.e-v.s)^(e-v.s);
if ((s.x*a2-e.x*a1)%(a2-a1))
return {inf,inf};
return Point({(s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)});
}
};
ll n;
map <Point,ll> mp;
vector <Line> v;
ll flag=0;
void check(Line x)
{
ll ans=0;
vector <Point> add;
for (auto z:v)
{
ll op=x.linecrossline(z);
if (op==0)
continue;
else if (op==1)
ans++;
else
{
Point a=x.crosspoint(z);
add.pb(a);
}
}
sort(all(add));
Point pre={inf,inf};
ll cnt=0;
for (auto z:add)
{
if (z.x==inf)
continue;
if (z==pre)
cnt++;
else
{
cnt=1;
pre=z;
}
ll ck=cnt+ans;
if (mp.count(z))
ck-=3;
if (ck>=n)
{
flag=1;
printf("YES\n");
printf("%lld %lld\n",z.x,z.y);
return;
}
}
}
void sol()
{
mp.clear(),v.clear();
flag=0;
cin>>n;
for (ll i=1;i<=n;i++)
{
ll x,y;
cin>>x>>y;
mp[{x,y}]++;
Point a={x,y};
v.pb({a,{a.x,a.y+1}});
v.pb({a,{a.x+1,a.y}});
v.pb({a,{a.x+1,a.y+1}});
v.pb({a,{a.x+1,a.y-1}});
}
for (ll i=0;i<4;i++)
{
check(v[i]);
if (flag)
return;
}
printf("NO\n");
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int tt=1;
cin>>tt;
while (tt--)
sol();
return 0;
}
/*
3
2
1 1
2 2
4
0 1
1 0
3 1
4 0
5
0 1
1 0
1 2
2 2
4 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 0