QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732501 | #9475. Pangu and Stones | SSAABBEERR | TL | 0ms | 0kb | C++20 | 5.0kb | 2024-11-10 14:53:58 | 2024-11-10 14:54:00 |
Judging History
answer
#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define endl "\n"
// #define ll long long
#define int long long
#define fi first
#define se second
using namespace std;
#define pii pair<int, int>
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
#define pre(i, a, b) for(int i = a; i >= b; i -- )
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
mt19937_64 rnd(time(0));
const int N = 1e6 + 10;
int n, m;
const double eps = 1e-10;
struct Point
{
double x, y;
Point(double x = 0, double y = 0):x(x), y(y){}
Point operator - (Point B){return Point(x - B.x, y - B.y);}
}p[N];
int cmp1(Point x,Point y){
return x.x!=y.x ? x.x<y.x : x.y<y.y;
}
double compare(Point a,Point b,Point c){ //计算极角
Point A={b.x-a.x,b.y-a.y};
Point B={c.x-a.x,c.y-a.y};
return A.x*B.y-A.y*B.x;
}
double cross(Point a,Point b,Point c){ //叉积
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int dcmp(double x)
{
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
double Cross(Point a, Point b)
{
return a.x * b.y - b.x * a.y;
}
bool ck(Point a, Point b, Point c, Point d)
{
double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a);
double c3 = Cross(d - c, a - c), c4 = Cross(d - c, b - c);
return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
int sgn(double x)
{
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
return 1;
}
double dot(Point a, Point b)
{
return a.x * b.x + a.y * b.y;
}
bool ckk(Point pi, Point pj, Point q)
{
if((q.x - pi.x) * (pj.y - pi.y) == (pj.x - pi.x) * (q.y - pi.y) && min(pi.x, pj.x) <= q.x && q.x <= max(pi.x, pj.x) && min(pi.y, pj.y) <= q.y && q.y <= max(pi.y, pj.y))
{
return true;
}
return false;
}
bool ck1(Point a, Point b, Point c, Point d)
{
double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a);
double c3 = Cross(d - c, a - c), c4 = Cross(d - c, b - c);
if(!sgn(c1) || !sgn(c2) || !sgn(c3) || !sgn(c4))
{
bool f1 = ckk(a, b, c);
bool f2 = ckk(a, b, d);
bool f3 = ckk(c, d, a);
bool f4 = ckk(c, d, b);
bool f = (f1 | f2 | f3 | f4);
return f;
}
return (sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0);
}
int nn, mm;
int stk[N], tp = 0;
void tubao()
{
sort(p + 1, p + nn + 1, cmp1);
for(int i=1;i<=nn;i++){
while(tp>1&&cross(p[stk[tp-1]],p[stk[tp]],p[i])<=0)tp--;
stk[++tp]=i;
}
int t=tp;
for(int i=nn-1;i>=1;i--){
while(tp>t&&cross(p[stk[tp-1]],p[stk[tp]],p[i])<=0)tp--;
stk[++tp]=i;
}
}
int kk(Point p, Point s, Point e)
{
Point x = p - s, y = p - e;
if(x.x * y.y == x.y * y.x) return true;
return false;
}
bool ck2(Point a, Point b, Point c, Point d)
{
// cout<<kk(b, c, d);
if(kk(a, c, d) && kk(b, c, d)) return true;
return false;
}
Point d[10];
string s[110];
int dis[110][110], st[110][110];
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
void bfs()
{
queue<pair<double, double>>q;
q.push({0, 0});
rep(i, 0, 30)rep(j, 0, 30)dis[i][j] = 1e9, st[i][j] = 0;
st[0][0] = 1;
dis[0][0] = 0;
while(q.size())
{
auto [x, y] = q.front();
q.pop();
// cout<<x<<" "<<y<<endl;
rep(i, 0, 7)
{
int tx = x + dx[i], ty = y + dy[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n || st[tx][ty] || s[tx][ty] == '#') continue;
tp = 0, nn = 0;
int f = 0, tot = 0, ff = 0;
int f1 = 0, f2 = 0;
rep(j, 1, 3)
{
p[++nn] = d[j];
rep(k, j + 1, 3)
{
if(ck({x, y}, {tx, ty}, d[j], d[k])) f = 1;
if(ck1({x, y}, {tx, ty}, d[j], d[k]) && !ck({x, y}, {tx, ty}, d[j], d[k])) tot ++ ;
if(ck2({x, y}, {tx, ty}, d[j], d[k])) ff = 1;
if(ckk(d[j], d[k], {x, y})) f1 = 1;
if(ckk(d[j], d[k], {tx, ty})) f2 = 1;
}
}
p[++nn] = {tx, ty};
tubao();
int fff = 0;
rep(j, 1, tp)
{
if(p[stk[j]].x == tx && p[stk[j]].y == ty) fff = 1;
}
// if(x==2&&y==1&&tx==2&&ty==2)cout<<fff;
if(f) continue;
if(!ff && tot == 3) continue;
if(tot == 1 && !fff) continue;
if(tot == 2 && !fff && !ff) continue;
if(f1 && f2 && tot == 2 && !ff) continue;
// if(tx==2&&ty==2)cout<<x<<" "<<y;
dis[tx][ty] = dis[(int)x][(int)y] + 1;
q.push({tx, ty});
st[tx][ty] = 1;
}
}
}
//ck 线段相交,无端点
//ckk 点是否在线段上
// ck1 线段是否相交,有端点
// ck2 线段是否共线
void solve()
{
rep(i, 1, 500000000)cout<<1;
}
signed main()
{
IOS;
int _;
_ = 1;
// cin >> _;
while(_ -- )
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 2 1 2 3 3 2 3 1 2 3 4 3 3 1 2 3 4
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...