oj.uz

Submission #632493

# Submission time Handle Problem Language Result Execution time Memory
632493 2022-08-20T07:48:32 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
20 / 100
 100 ms 8900 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;
    rez=abs(rez);
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;
    if(A.ang>B.ang)
        swap(A,B);
    if(C.ang>=A.ang&&C.ang<=B.ang)
        if(aria(A,C)+aria(B,C)>=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 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 47 ms 584 KB Output is correct
4 Correct 77 ms 668 KB Output is correct
5 Execution timed out 219 ms 1160 KB Time limit exceeded
6 Execution timed out 111 ms 1108 KB Time limit exceeded
7 Incorrect 26 ms 2004 KB Output isn't correct
8 Incorrect 10 ms 980 KB Output isn't correct
9 Execution timed out 274 ms 1088 KB Time limit exceeded
10 Incorrect 13 ms 1108 KB Output isn't correct
11 Incorrect 15 ms 1252 KB Output isn't correct
12 Execution timed out 591 ms 2016 KB Time limit exceeded
13 Execution timed out 282 ms 2880 KB Time limit exceeded
14 Execution timed out 234 ms 3692 KB Time limit exceeded
15 Execution timed out 1095 ms 4588 KB Time limit exceeded
16 Execution timed out 1094 ms 8900 KB Time limit exceeded
17 Execution timed out 1098 ms 8812 KB Time limit exceeded
18 Runtime error 75 ms 5124 KB Execution killed with signal 11
19 Runtime error 60 ms 5168 KB Execution killed with signal 11
20 Execution timed out 142 ms 7344 KB Time limit exceeded