oj.uz

답안 #632507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632507 2022-08-20T08:29:49 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
10 / 100
 100 ms 10076 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    ll 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;

    ll a1=B.y-A.y;
    ll b1=A.x-B.x;
    ll c1=-a1*A.x-b1*A.y;

    ll a2=C.y;
    ll b2=-C.x;
    ll c2=0;

    ld coef=a2*b1-a1*b2;
    if(coef==0)
        return 0;
    ld y=ld(-a2*c1)/coef;
    ld x=ld(-b2*y)/a2;
    if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0)
        if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0)
            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;
}

Compilation message

circuit.cpp: In function 'bool intersect(point, point, point)':
circuit.cpp:62:8: warning: unused variable 'c2' [-Wunused-variable]
   62 |     ll c2=0;
      |        ^~

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Execution timed out 112 ms 484 KB Time limit exceeded
4 Execution timed out 269 ms 532 KB Time limit exceeded
5 Execution timed out 585 ms 972 KB Time limit exceeded
6 Execution timed out 632 ms 900 KB Time limit exceeded
7 Execution timed out 1090 ms 1356 KB Time limit exceeded
8 Execution timed out 379 ms 784 KB Time limit exceeded
9 Execution timed out 693 ms 816 KB Time limit exceeded
10 Execution timed out 627 ms 900 KB Time limit exceeded
11 Execution timed out 735 ms 956 KB Time limit exceeded
12 Execution timed out 1076 ms 1364 KB Time limit exceeded
13 Execution timed out 1041 ms 1748 KB Time limit exceeded
14 Execution timed out 463 ms 2300 KB Time limit exceeded
15 Execution timed out 1068 ms 2732 KB Time limit exceeded
16 Execution timed out 1085 ms 5024 KB Time limit exceeded
17 Execution timed out 1083 ms 5084 KB Time limit exceeded
18 Runtime error 68 ms 10076 KB Execution killed with signal 11
19 Runtime error 64 ms 10044 KB Execution killed with signal 11
20 Execution timed out 1088 ms 5068 KB Time limit exceeded