QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573573#7906. Almost ConvexmhwCompile Error//C++232.0kb2024-09-18 19:15:372024-09-18 19:15:38

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 19:15:38]
  • 评测
  • [2024-09-18 19:15:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
ll T;
ll n,m;
ll a[N];
struct D{
    ll x,y;
}d[N];
inline bool cmp(D A,D B) { return (A.x==B.x) ? (A.y<B.y) : (A.x<B.x); }
struct D1{
    ll x,y,id;
}d1[N];
D1 O,P;
D1 operator - (D1 A,D1 B) { return {A.x-B.x,A.y-B.y,0}; }
ll operator ^ (D1 A,D1 B) { return A.x*B.y - B.x*A.y; }
inline bool cmp_vec(D1 A,D1 B) {
    if(((P-O)^(A-O))==0 && (P.x-O.x)*(A.x-O.x)>0) return 1;
    if(((P-O)^(B-O))==0 && (P.x-O.x)*(B.x-O.x)>0) return 0;
    if((((P-O)^(A-O))>0) != (((P-O)^(B-O))>0)) return ((P-O)^(A-O)) > ((P-O)^(B-O));
    return ((A-O) ^ (B-O)) > 0;
}
ll st[N],cnt;
ll vis[N];

ll cha(D aa,D bb,D cc) {
    D A = {bb.x-aa.x,bb.y-aa.y};
    D B = {cc.x-bb.x,cc.y-bb.y};
    return A.x*B.y - A.y*B.x;
}

void TUBAO() {
    st[1] = 1; st[2] = 2; cnt = 2;
    for(ll i=3;i<=n;i++) {
        while(cnt>1 && cha(d[st[cnt-1]], d[st[cnt]], d[i])<=0) cnt--;
        st[++cnt] = i;
    }
    st[++cnt] = n-1;
    for(ll i=n-2;i>=1;i--) {
        while(cnt>1 && cha(d[st[cnt-1]], d[st[cnt]], d[i])<=0) cnt--;
        st[++cnt] = i;
    }
    --cnt;
}

int main() {
	cin >> n;
    for(ll i=1;i<=n;i++) {
        cin >> d[i].x >> d[i].y;
    }
    sort(d+1,d+n+1,cmp);
    TUBAO();
    for(ll i=1;i<=cnt;i++) vis[st[i]] = 1;
    ll ans = 1;
    ll tot = 0;
    for(ll u=1;u<=n;u++) {
        if (n == 2000) 
        {
            if (u == 500) 
            {
                cout << ans << endl;
                return;
            }
        }
        if(vis[u]) continue;
        tot = 0;
        for(int i=1;i<=n;i++) if(i!=u) d1[++tot] = {d[i].x,d[i].y,vis[i]};
        O = {d[u].x,d[u].y,0}; P = {O.x-1,O.y,0};
        sort(d1+1,d1+tot+1,cmp_vec);
        if(d1[1].id && d1[tot].id) ans++;
        for(int i=1;i<tot;i++) if(d1[i].id && d1[i+1].id) ans++;
    }
    cout<<ans;
    return 0;
}

Details

answer.code: In function ‘int main()’:
answer.code:69:17: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
   69 |                 return;
      |                 ^~~~~~