QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #103388 | #4383. Laser | sine_and_cosine# | AC ✓ | 173ms | 4864kb | C++17 | 6.5kb | 2023-05-05 16:52:49 | 2023-05-05 16:52:51 |
Judging History
answer
#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <array>
#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define ite2(x,y,arr) for(auto [x,y]:arr)
#define pdd pair<double, double>
#define ite(i,arr) for(auto &i:arr)
#define MID(l,r) int mid=(l+r)>>1
#define ALL(arr) arr.begin(),arr.end()
#define AXY(a,x,y) int x=a.first,y=a.second
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define FTY
double inf = 521.1145314;
namespace G {
#ifdef FTY
const double eps = 1e-8;
const double PI = acos(-1);
struct Point {
double x, y;
Point() {
x = 0, y = 0;
}
Point(double x, double y) {
this->x = x;
this->y = y;
}
};
bool operator<(Point a, Point b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
Point operator +(Point a, Point b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator -(Point a, Point b) {
return Point(a.x - b.x, a.y - b.y);
}
Point operator *(double a, Point b) {
return Point(a * b.x, a * b.y);
}
Point operator *(Point b, double a) {
return Point(a * b.x, a * b.y);
}
Point operator /(Point b, double a) {
return Point(b.x / a, b.y / a);
}
double len(Point a) {
return sqrt(a.x * a.x + a.y * a.y);
}
double dis(Point a, Point b) {
return len(a - b);
}
bool operator ==(Point a, Point b) {
return dis(a, b) <= eps||a.x==inf||b.x==inf;
}
bool operator !=(Point a, Point b) {
return !(a == b);
}
double operator *(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
double operator ^(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
double getAngel(double b, double a, double c) {
return acos((a * a + c * c - b * b) / (2 * a * c));
}
double getAngel(Point a, Point b) {
return acos(a * b / len(a) / len(b));
}
Point inter(Point p, Point v, Point q, Point w) {
if (fabs(v ^ w) <= eps) {
return { inf,inf };
}
Point u = p - q;
double t = (w ^ u) / (v ^ w);
return p + t * v;
}
#endif
}
using namespace G;
#define int ll
const int mod = (int)1e9 + 7;
//template <class T>
//T __gcd(T a, T b) {
// if (a < b) swap(a, b);
// return b ? __gcd(b, a % b) : a;
//}
template <class T>
T __lcm(T a, T b) {
T num = __gcd(a, b);
return a / num * b;
}
inline int lowbit(int num) { return num & (-num); }
inline int qmi(int a, int b) {
a %= mod;
ll res = 1;
while (b) {
if (b & 1) res = (ll)res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
int inv(int num) {
return qmi(num, mod - 2);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
vc<Point> arr(n);
rep(i, 0, n) {
cin >> arr[i].x >> arr[i].y;
}
if (n < 3) {
cout << "YES\n";
continue;
}
else {
Point vec[4] = { {1,0},{0,1},{1,1},{1,-1} };
int __ = 20;
int flag = 0;
while (__--) {
int p1 = rand() % n, p2 = rand() % n;
while (p1 == p2) {
p2 = rand() % n;
}
rep(i, 0, 4) {
rep(j, 0, 4) {
if (fabs((vec[i]) ^ (vec[j])) > eps) {
Point p= inter(arr[p1], vec[i], arr[p2], vec[j]);
flag = 1;
rep(t, 0, n) {
int ok = 0;
rep(tt, 0, 4) {
Point v = arr[t] - p;
if (fabs(v ^ vec[tt]) <= eps) {
ok = 1;
break;
}
}
flag *= ok;
if (!flag) break;
}
}
if (flag) break;
}
if (flag) break;
}
if (flag) break;
}
/*rep(i, 2, n) {
if (fabs((arr[0] - arr[1]) ^ (arr[0] - arr[i])) > eps) {
swap(arr[i], arr[2]);
break;
}
}
if (fabs((arr[0] - arr[1]) ^ (arr[0] - arr[2])) <= eps) {
cout << "YES\n";
continue;
}
int flag = 0;
rep(i, 0, 4) {
rep(j, 0, 4) {
rep(k, 0, 4) {
Point a = inter(arr[0], vec[i], arr[1], vec[j]);
Point b = inter(arr[0], vec[i], arr[2], vec[k]);
Point c = inter(arr[2], vec[k], arr[1], vec[j]);
if (!(a.x==inf&&b.x==inf&&c.x==inf)&&a==b&&a==c&&b==c) {
flag = 1;
rep(t, 0, n) {
int ok = 0;
rep(tt, 0, 4) {
Point v = arr[t] - a;
if (fabs(v ^ vec[tt]) <= eps) {
ok = 1;
break;
}
}
flag *= ok;
if (!flag) break;
}
}
if (flag) break;
}
if (flag) break;
}
if (flag) break;
}*/
if (flag) cout << "YES\n";
else cout << "NO\n";
}
}
return 0;
}
/*
2
6
1 1
1 3
2 2
3 1
3 3
3 4
7
1 1
1 3
2 2
3 1
3 3
1 4
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 173ms
memory: 4864kb
input:
116 4 -10 0 10 0 5 5 -5 -5 4 -10 0 10 0 0 10 0 -10 4 -1 0 1 0 2 0 3 0 4 0 1 0 2 0 3 0 4 4 100 100 10000 10000 100000 100000 -100 -100 4 -100 100 -10000 10000 -100000 100000 100 -100 6 1 1 1 3 2 2 3 1 3 3 3 4 7 1 1 1 3 2 2 3 1 3 3 1 4 3 4 4 1236833 14678 1232056 9901 1237055 9790 1231834 15011 4 1236...
output:
YES YES YES YES YES YES YES NO YES NO NO YES NO NO YES YES NO NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES NO NO YES NO NO NO YES YES YES NO NO YES YES NO NO NO NO NO YES YES NO YES NO NO YES NO YES NO NO NO NO YES YES YES NO YES YES YES NO YES YES NO YES NO YES YES NO YES NO...
result:
ok 116 lines