QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431644 | #7894. Many Many Heads | Botter | WA | 0ms | 3688kb | C++14 | 2.1kb | 2024-06-05 20:49:35 | 2024-06-05 20:49:36 |
Judging History
answer
//
// Created by Botter on 2024/6/5.
//
#include <bits/stdc++.h>
using namespace std;
const long long N = 2005;
struct point{
long long x,y;
}s[N],p[N],yu[N];
long long n,st[N],top,res[N];
bool vis[N],vis1[N];
bool cmp(const point a , const point b){
if (a.y == b.y){
return a.x<b.x;
}
return a.y < b.y;
}
bool mult(point a,point b,point c){
return (a.x-c.x) *(b.y-c.y) >= (b.x-c.x)*(a.y-c.y);
}
long long corss(point a,point b,point c){
return abs((a.x-c.x) *(b.y-c.y) - (b.x-c.x)*(a.y-c.y));
}
bool sing(point a,point b ,point c,point p){
long long S =corss(a,b,c);
long long s1=corss(a,b,p);
long long s2=corss(a,c,p);
long long s3=corss(b,c,p);
return S == s1+s2+s3;
}
void Se(){
long long i,len;
top=1;
sort(s,s+n,cmp);
res[1]=1,res[2]=2;
for (i=2;i<n;++i){
while (top&&mult(s[i],s[res[top]],s[res[top-1]])) top--;
res[++top]=i;
}
len = top;
res[++top] = n-2;
for (i = n-3;i>=0;--i){
while(top!=len&&mult(s[i],s[res[top]],s[res[top-1]])) top--;
res[++top]=i;
}
}
int main() {
long long ly=0,lb=0;
long long ans=1;
ios::sync_with_stdio(0);cin.tie();cout.tie();
cin >> n;
if (n == 3) {cout << 1 <<endl; return 0;}
for (long long i=0;i<n;++i)cin>>s[i].x >> s[i].y;
Se();
for (long long i = 0 ; i < top ; ++i){
p[lb++] = s[res[i]];
vis[res[i]] = 1;
}
for (long long i = 0 ; i < n ; i++){
if (!vis[i]) yu[ly++] = s[i];
}
for (long long i = 0 ; i < lb;++i){
point a = p[i],b=p[(i+1)%lb];
for (int j = 0;j<ly;++j){
point c = yu[j];
int k = 0;
long long cnt = 0;
for ( k = 0 ; k < ly ; ++k){
if (j == k) continue;
if (sing(a,b,c,yu[k])) {//有点在三角内
break;
}
else{
cnt++;
}
}
if (cnt == ly-1) ans++;
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3688kb
input:
6 )) ((() [()] ()[()]() ([()]) ([])([])
output:
1
result:
wrong output format YES or NO expected, but 1 found [1st token]