oj.uz

Submission #632499

# Submission time Handle Problem Language Result Execution time Memory
632499 2022-08-20T07:53:40 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
20 / 100
 100 ms 5072 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].ang!=v[b].ang)
        return v[a].ang<v[b].ang;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int cur=0;
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
ll aria(point A, point B)
{
    ll rez=1LL*A.x*B.y-1LL*A.y*B.x;
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;
    int s1=aria(A,C);
    if(s1<0)
        s1=-1;
    else if(s1>0)
        s1=1;
    else if(s1==0)
    {
        if(C.x>A.x)
            return 1;
        return 0;
    }
    int s2=aria(B,C);
    if(s2<0)
        s2=-1;
    else if(s2>0)
        s2=1;
    else if(s2==0)
    {
        if(C.x>B.x)
            return 1;
        return 0;
    }
    if(s1!=s2)
        if(abs(aria(A,C))+abs(aria(B,C))>=abs(aria(A,B)))
            return 1;
    return 0;
}
bool checkgood(int i)
{
    if(cur==0)
        return 1;
    point a=v[cur];
    int lft=cur-1;
    if(lft<1)
        lft=n;
    point b=v[lft];
    if(intersect(a,b,v[i]))
        return 0;
    int rgt=cur+1;
    if(rgt>n)
        rgt=1;
    b=v[rgt];
    if(intersect(a,b,v[i]))
        return 0;
    return 1;
}
vector<int> sol;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    /*sort(angle+1,angle+n+1,comp);
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }*/
    for(int i=1;i<=n;i++)
    {
        bool ok=1;
        for(int j=1;j<=n&&ok;j++)
            {
                int nxt=j+1;
                if(j==n)
                    nxt=1;
                if(j!=i&&nxt!=i)
                    if(intersect(v[j],v[nxt],v[i]))
                        ok=0;
            }
        if(ok)
            sol.push_back(i);
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 61 ms 392 KB Output is correct
4 Correct 100 ms 424 KB Output is correct
5 Incorrect 8 ms 468 KB Output isn't correct
6 Incorrect 7 ms 468 KB Output isn't correct
7 Incorrect 15 ms 700 KB Output isn't correct
8 Incorrect 6 ms 464 KB Output isn't correct
9 Execution timed out 352 ms 652 KB Time limit exceeded
10 Incorrect 11 ms 420 KB Output isn't correct
11 Incorrect 10 ms 464 KB Output isn't correct
12 Execution timed out 654 ms 768 KB Time limit exceeded
13 Incorrect 29 ms 980 KB Output isn't correct
14 Execution timed out 212 ms 1236 KB Time limit exceeded
15 Execution timed out 1075 ms 1404 KB Time limit exceeded
16 Execution timed out 1089 ms 2612 KB Time limit exceeded
17 Incorrect 90 ms 2524 KB Output isn't correct
18 Runtime error 61 ms 5072 KB Execution killed with signal 11
19 Runtime error 66 ms 5072 KB Execution killed with signal 11
20 Incorrect 74 ms 2604 KB Output isn't correct