QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639404 | #5426. Drain the Water Tank | Godwang | TL | 1ms | 5756kb | C++23 | 3.0kb | 2024-10-13 19:22:44 | 2024-10-13 19:22:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
const int N=1e5+10;
/////////////////////
int tt;
int n;
struct Point
{
ll x,y;
Point()
{
}
Point(ll x,ll y):x(x),y(y){}
Point operator + (Point B)
{
return Point(x+B.x,y+B.y);
}
Point operator - (Point B)
{
return Point(x-B.x,y-B.y);
}
};
typedef Point Vector;
ll Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Point p[N],ch[N];
int kaishi;
set<int > se;
/////////////////////
int pre(int u)
{
if(u==0)
{
return n-1;
}
return u-1;
}
int nxt(int u)
{
if(u==n-1)
{
return 0;
}
return u+1;
}
/////////////////////
/////////////////////
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("ain.txt","r",stdin);freopen("aout.txt","w",stdout);
cin>>n;
rep(i,0,n-1)
{
cin>>p[i].x>>p[i].y;
}
kaishi=0;
while (1)
{
int qian=pre(kaishi);
if(Cross( p[kaishi]-p[qian] , p[1]-p[kaishi])!=0)
{
break;
}
kaishi=qian;
}
int dier=1;
while (1)
{
int hou=nxt(dier);
if(Cross( p[hou]-p[dier] , p[dier]-p[kaishi])!=0)
{
break;
}
dier=hou;
}
int now=kaishi;
bool fla=1;
int a=kaishi,b=dier,c;
se.insert(a);
se.insert(b);
//
//cout<<kaishi<<" "<<dier<<endl;
// exit(0);
while (1)
{
if(fla==0)
{
a=b;
b=c;
}
if(fla==0&&a==kaishi)
{
break;
}
se.insert(a);
se.insert(b);
fla=0;
c=nxt(b);
//
while (1)
{
if(Cross(p[c]-p[b],p[b]-p[a])!=0)
{
break;
}
c=nxt(c);
}
se.insert(c);
}
n=se.size();
//
// cout<<n<<endl;
int cnt=0;
for(auto i:se)
{
ch[cnt].x=p[i].x;
ch[cnt].y=p[i].y;
cnt++;
}
a=0;
b=1;
c=2;
fla=1;
int ans=0;
while(1)
{
if(a==0&&fla==0)
{
break;
}
//
if(p[a].y>p[b].y&&p[b].y<p[c].y)
{
if(Cross(ch[b]-ch[a],ch[c]-ch[b])>0)
{
ans++;
}
}
if(p[a].y>p[b].y&&p[b].y==p[c].y)
{
int d=nxt(c);
// //
// cout<<d<<endl;
if(Cross(ch[c]-ch[b],ch[d]-ch[c])>0)
{
ans++;
}
}
a=nxt(a);
b=nxt(b);
c=nxt(c);
fla=0;
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5708kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
8 4 4 0 4 0 2 1 2 2 2 2 0 3 0 4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
7 1 0 3 4 0 3 1 2 2 3 1 1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 0 0 170 0 140 30 60 30 0 70
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: -100
Time Limit Exceeded
input:
5 0 0 1 2 1 5 0 2 0 1